# 題目: 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...

# 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 、 b 、 c...

# 遊戲說明 這是一個五子棋遊戲，規則就如同大家熟悉的那樣，先使 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...

# 題目: 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...

# 題目: 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...

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

# 題目: 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...

# 題目: 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 即可 # 參考程式碼...