# 題目: UVa 168 - Theseus and the Minotaur # 題目說明 一個勇者正在迷宮中追逐怪物，怪物會怕光線 勇者每隔一段距離就會插上一個蠟燭，怪物就不會走到那裡 持續下去，怪物最終會被困在一個地方 求所有蠟燭的位置及怪物最後被困住的位置 (怪物會優先往字母小 (a) 的地方走) INPUT: 每筆資料會先有一個字串，代表能走的路 接著會有兩個字元 m 、 t 和一個整數 k m 代表怪物一開始的位置 t 代表勇者一開始的位置 k 代表每走幾步會插一個蠟燭 當字串為 # 時結束 OUTPUT: 有插蠟燭的位置及怪物最後被困住的位置 # 解題方法 先將地圖建表，...

# 題目: UVa 11034 - Ferry Loading IV # 題目說明 有車子想要渡河，目前唯一渡河的方式為搭船 船只有一艘且長度有限，求所有車子到達對岸時船的趟數 INPUT: 第一行有一個整數 c ，代表有 c 筆資料 每筆測資第一行有兩個整數 l 、 m l 代表船的長度 m 代表等待過河的車子數量 接下來有 m 行，每行有一個整數和一個字串 整數代表車子的長度 字串代表它處於河的哪一邊 OUTPUT: 將所有車子運送到對岸，船需要開的趟數 # 解題方法 以兩個 queue 分別存左岸及右岸的車子的長度 接著跑迴圈直到兩個 queue...

# 題目: UVa 10901 - Ferry Loading III # 題目說明 有車子想要渡河，目前唯一渡河的方式為搭船 船只有一艘且容量有限，求所有車子到達對岸的時間 INPUT: 第一行有一個整數 c ，代表有 c 筆資料 每筆測資第一行有三個整數 n 、 t 、 m n 代表船能容納的車子數量 t 代表船開到對岸的時間 m 代表等待過河的車子數量 接下來有 m 行，每行有一個整數和一個字串，整數代表車子到岸邊的時間，字串代表它處於河的哪一邊 OUTPUT: 輸出每輛車子到達對岸的時間 每筆資料以空行隔開 # 解題方法 以兩個 queue...

# 題目: UVa 10172 - The Lonesome Cargo Distributor # 題目說明 有一輛貨車跟數個站點，貨車與站點的容量有限制 貨車每到一個站會執行以下動作 將車上的貨物卸下，如果是目標貨物直接卸下，否則放到站點的 queue 中 將站點中的貨物裝到車上 移動到下一個站點 花費時間: 每次裝貨及卸貨都會花費 1 分鐘 移動到下一個站點會花費 2 分鐘 求所有貨物放到目標站點所花費的時間 INPUT: 第一行有一個整數 SET ，代表有幾筆資料 每筆資料的第一行有三個整數 N 、 S 、 Q N 代表有幾站、 S 代表貨車可裝載貨物量、 Q 代表站點中...

# 題目: UVa 1062 – Containers # 題目說明 船運送貨物到港口，貨物需要依 A 到 Z 的順序排序 字母大的貨物在下，且字母大的貨物不能放在比它小的上方 求貨物至少要先堆成幾堆才能達成 INPUT: 每筆資料輸入一個字串，代表貨物到港口的順序 當輸入為 end 時結束程式 OUTPUT: 先輸出第幾個 case 接著輸出需要的最小 stack 數 # 解題方法 其實這題就是在求 LIS : 最長嚴格遞增子陣列 利用 greedy演算法 求出 LIS # 參考程式碼 #include <iostream>#include...

# 題目: UVa 732 - Anagrams by Stack # 題目說明 給你兩個字串及一個 stack ，找出所有能使前者變成後者的所有 input 、 output 組合 INPUT: 每筆資料輸入兩個字串，起始字串及目標字串 OUTPUT: 輸出起始字串能透過 stack 轉變為目標字串的所有組合 # 解題方法 使用 dfs，每次將字串 push 及 pop ，最後如果符合目標字串則輸出 # 參考程式碼 #include <iostream>#include <stack>using namespace std;string in,...

# 題目: UVa 514 - Rails # 題目說明 有一個火車站，出去及進來都只有一條路 有一對列按照編號順序排列的火車 它們是否能按照特定順序出車站？ INPUT: 每筆資料的第一行有一個整數 n ，代表有 n 個火車 接著有 n 個整數，代表火車出站的順序 當第一個順序為 0 時，結束這筆資料 當 n 為 0 時，結束程式 OUTPUT: 當順序為可行時，輸出 Yes ，否則輸出 No # 解題方法 用 stack a 儲存資料，按照順序找到火車 (判斷 stack a 及 stack b 的 top ) 並將這台火車前面的火車都 push 到 stack b 如果過程中...

# 題目: UVa 11995 - I Can Guess the Data Structure! # 題目說明 你能猜到資料結構嗎？ 給你一些 push 和 pop data，找出資料結構 INPUT: 每筆資料的第一行有一個整數 n ，代表接下來有 n 行 每行有兩個整數，前者代表指令， 1 為 push ， 2 為 pop ，後者代表數字 OUTPUT: stack queue priority queue 都不是 impossible 兩種以上容器符合 not sure # 解題方法 分別 push 到 3 種容器中做模擬，看有幾個符合 # 參考程式碼 #include...

# 題目: UVa 10954 - Add All # 題目說明 題目說明了你的目標: 加全 例如 1 + 2 + 3 先 1 + 2 cost 3 再 3 + 3 cost 6 總共 cost 9 INPUT: 每筆資料的第一行有一個整數 N ，代表接下來有 N 個整數 當 N 為 0 時結束程式 OUTPUT: 輸出全部相加所需最少的 cost # 解題方法 用 priority queue 儲存資料 (升冪排序) 每次取最前 (小) 兩個做相加即可 # 參考程式碼 #include <iostream>#include <queue>using...

# 題目: UVa 1203 - Argus # 題目說明 我們在 Argus 註冊了很多 Register 你的目標是找到錢 K 個 Register INPUT: 每行輸入 3 個字串 Register 或 # ，當輸入為 # 結束 Register 的編號 Register 的頻率 最後有一個整數 K ，代表要輸出幾個 Register OUTPUT: 輸出 K 個 Register 的編號，如果頻率相同，則編號小的優先輸出 # 解題方法 用 priority queue 儲存編號及頻率 (升冪排序) 每次找到一個 Register，將它的現在時間加上原本頻率再度 push 回...