[試題] 107 資工轉系考 程式上機

[isaswa (漆黒丸)]

考試時間：120分鐘

1. 平行四邊形
   給定A,B,C三點，找出對應的D,E,F，使得ABDC、ABCE，AFBC皆為平行四邊形

   輸入：A,B,C三點平面座標(x,y)
   輸出：D,E,F三點平面座標(x,y)

   解：基本輸入輸出、高中數學

2. 違停腳踏車與停車位
   地圖上會有n個停車格與m個違停腳踏車
   每個停車格i會有一個容量ci，代表最多能停放幾輛腳踏車
   將每一台違停腳踏車移動到離它最近的停車位
   「距離」定義為 d=|x1-x2|+|y1-y2|
   如果該停車位的容量滿了，就移動到第二近的停車位
   如果有兩個最近的停車位，移動到x座標比較小的那個
   如果x座標也一樣，移動到y座標比較小的那個
   保證所有停車格的容量總和一定比違停車輛數還多

   輸入：一個整數n，接下來n行數組為n個相異停車位的座標與容量(xi,yi,ci)
         一個整數m，接下來m行數組為m個相異的違停腳踏車座標(xi,yi)
         n≦10, m≦100000, -10000≦x,y≦10000

   輸出：輸入的車輛順序即為移動車輛的順序
         跟據此順序輸出各停車格最終停放的腳踏車數量

   解：條件判斷、模擬(不須優化)


3. 朋友距離                 欺負BANG緣人沒朋友喔
   給定n(≦11)個人，人名以大寫字母的字典序前n個字母表示(A,B,C...)
   給定m個朋友關係，將n個人排成一列
   請最小化隊列之中是朋友的兩人之間距離的最大值

   舉例：假設現在有5個人，其中AB,BE,CE為朋友
         隊伍ABCDE之中，AB的距離為1，BE的距離為3，CE的距離為2
         則此例中的朋友距離最大值為3

   輸入：第一行為兩個整數n,m
         接下來m行為兩個大寫字母X Y(中間空一格)，表示此兩人互為朋友
         95%測資：N≦10
          5%測資：N≦11

   輸出：第一行請輸出最大朋友距離的最小值(整數)
         第二行請輸出具有此最小值的隊伍(字母間空1格)，以字典序最前者為解

   提示：N≦11的測資請使用剪枝，也就是當你發現目前的排法之朋友距離最大值
         已經超過你目前計算過的最小值時，就不需要繼續嘗試這個排法的後續了

   解：遞迴，暴搜會得95分 (題目已經告訴你全部要怎麼做了)

-------------------------

碎碎念：邦鋒整場考試一直在提示大家要怎麼做
        還一直強調只有第三題的5分要優化 XD

--
◣▄      ▄◢□╳                 .╴╴╴╴╴╴╴╴╴╴╴.            ψLad╳□
◤  ▼◥\▼ ◥╳  夜々（やや）     ◎機巧少女は傷つかない◎                   ╳
 ] ▊●  ● [ ︱                                    (.   ◙-*-. .=*￣*=-      ︱
▍ ◣  ﹀ ◢▋︱  [魔術迴路]  夜夜可愛いよ 夜夜～    `-.`-._上*`✽    ◙_╲   ︱
▍  ◢╳◣  ▋╳                        夜夜可愛いよ    ￣` 下☽)-╲╳╱)￣)‵╳
▋╱▇▅▇╲▍□╳金剛力（こんごうりき）    世界一可愛いよ。 ︶  `︶︶    ︶╳□

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 116.241.211.216
※ 文章網址: https://www.ptt.cc/bbs/DoubleMajor/M.1532082831.A.7DA.html
→ charlie1667: 可是你日文拿B+
結構學C的李大神開嘴
※ 編輯: isaswa (116.241.211.216), 07/20/2018 18:45:27
※ 編輯: isaswa (116.241.211.216), 07/20/2018 19:04:00
※ 編輯: isaswa (116.241.211.216), 07/20/2018 19:05:46
→ charlie1667: 是C+好嗎
※ 編輯: isaswa (116.241.211.216), 07/21/2018 13:11:10