# 題目: 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都為空 每趟運送在長度限制內運送愈多愈好 # 參考程式碼 #i

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

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

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

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

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

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

# 題目: 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 namespace std; in

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