# 題目: UVa 12908 - The book thief # 題目說明 給一個整數s，s符合1 + 2 + 3 + ... + n - x，也就是從1開始的累加，但其中少了一頁 其中n為總頁數、x為缺少的頁碼 求n與s INPUT: 每筆測資輸入一個整數s 當s為0時結束 OUTPUT: 輸出缺少的頁碼x與總頁數n # 解題方法 使用一個變數sum維持現在的累加值，i為累加的次數 當sum > s時，sum - s即為缺少的頁碼，i即為總頁數 # 參考程式碼 #include <iostream> using namespace std; static a

# A=B 是一款只有一條指令的編碼遊戲 A=B Steam 遊戲連結 Click here to see english version 2022.4.10 更新 第六章 2022.4.8 更新 第五章 2022.4.4 更新 第四章 2022.4.2 更新 第三章 2022.4.1 更新 第一、二章 # 第一章 A=B 指令說明 string1 = string2 將string1替換成string2 # 1-1 A to B 給一個包含a、b、c的字串，將字串中的a改成b a = b # 1-2 Uppercase 給一個包含a

# 遊戲說明 這是一個五子棋遊戲，規則就如同大家熟悉的那樣，先使5顆棋子連成一條線就獲勝 # 介面介紹 畫面中間為13 * 13大小的棋盤 左下角有一個text area，會顯示各種訊息 右下角有四個按鈕，分別為: vs player: 玩家與玩家對戰 vs computer: 玩家與電腦對戰 theme: 更換主題 restart: 重新開始遊戲 # 遊戲方式介紹 遊戲未開始前，能先選擇主題，總共有三種主題，每按一次theme按鈕就會跳至下一個主題 基本主題: 與一般五子棋一樣 岩石主題: 在13 * 13的場地中會隨機掉落10顆落石，落石掉落處視為牆壁，無法下棋子 海洋主題:

# 題目: UVa 10888 - Warehouse # 題目說明 給一個N * M的圖，圖上有4種符號B、X、.、# 你的目標是要找到使所有B移動到X(不可經過#)的最小距離 INPUT: 先輸入一個整數T，代表測資數 每筆測資輸入兩個整數N、M 接著輸入N * M個字元 OUTPUT: 輸出使所有B移動到X(不可經過#)的最小距離 # 解題方法 此題的解題概念為Minimum cost Maximum flow Maximum flow的部分使用Ford Fulkerson演算法 Minimum cost則使用佇列最佳化的bellman ford演算法，又稱Shortest Pat

# 題目: UVa 10806 - Dijkstra, Dijkstra # 題目說明 給一個無向圖，有N個點及M條邊，每條邊的capacity為1、有不同的cost 求從起點S走到終點T兩次，求總和最小的cost INPUT: 每筆測資先輸入兩個整數N、M 接下來有M行，每行輸入三個整數u、v、c，代表edge(u, v)的cost為c; OUTPUT: 輸出最小的cost，若無法從起點走到終點兩次則輸出Back to jail # 解題方法 此題的解題概念為Minimum cost Maximum flow Maximum flow的部分使用Ford Fulkerson演算法 Min

# 題目: UVa 10594 - Data Flow # 題目說明 給一個無向圖G，有N個點及M條邊，每條邊的capacity固定為K、有不同的cost 題目要求將大小為D的資料從起點S傳到終點T，求最小的cost INPUT: 每筆測資第一行輸入兩個整數N、M 接下來有M行，每行輸入三個整數u、v、c，代表edge(u, v)的cost為c 最後輸入兩個整數D、K OUTPUT: 輸出最小的cost，若無法將所有D資料傳至終點則輸出Impossible. # 解題方法 此題的解題概念為Minimum cost Maximum flow Maximum flow的部分使用Ford Fu

# 題目: UVa 11378 - Bey Battle # 題目說明 給N個點 (x, y平面座標)，每個點擴散一個正方形 (邊與x, y軸平行) 求正方形的最大邊長 INPUT: 每筆測資輸入一個整數N 接下來有N行，每行輸入兩個變數，為點的x, y座標 OUTPUT: 輸出正方形的最大邊長 # 解題方法 求正方形的最大邊長可視為找到最近的兩個點(Closest Pair) 只差在不是算兩點間的長度，而是取兩點x軸與y軸中較大的長度 # 參考程式碼 #include <iostream> #include <vector> #include <

# 題目: UVa 10245 - The Closest Pair Problem # 題目說明 給N個點 (x, y平面座標)，求這些點的最近距離 INPUT: 每筆測資輸入一個整數N 接下來有N行，每行輸入兩個變數，為點的x, y座標 OUTPUT: 輸出這些點的最近距離，如果>= 10000則輸出INFINITY # 解題方法 針對x做排序後，利用Divide and Conquer持續將所有點切成兩半 直到找到左半邊的最小值l、右半邊的最小值r 將d設為min(l ,r)，在中線 - d ~ 中線 + d的範圍內尋找更小的值 # 參考程式碼 #include &#

# 題目: UVa 11096 - Nails # 題目說明 給N個點 (x, y平面座標)，求這些點形成的凸包(Convex Hull)周長 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資輸入L、N，代表橡皮筋長度、點的數量 接下來有N行，每行輸入兩個變數(x, y)，為點的座標 OUTPUT: 輸出 MAX(凸包(Convex Hull)周長，L) # 解題方法 如果使用Graham's Scan演算法需要做極角排序 使用Andrew's Monotone Chain演算法 將凸包算出後再兩兩計算長度，加總即為周長 涉及小數，所以題中變數盡量用dou

# 題目: UVa 1206 - Boundary Points # 題目說明 給數個點 (x, y平面座標)，求這些點的凸包(Convex Hull) INPUT: 每筆測資輸入一行，輸入表示為(x,y)，代表一個點的平面座標 OUTPUT: 輸出組成凸包(Convex Hull)的點的座標 # 解題方法 如果使用Graham's Scan演算法需要做極角排序 使用Andrew's Monotone Chain演算法則跑兩次半邊，將所有點覆蓋 直接讀入座標後跑Andrew's Monotone Chain即可 # 參考程式碼 Graham's Scan