發表文章

目前顯示的是 2018的文章

Kotlin 與 Swift 語法對照:跨平台開發者 (2025年)

Kotlin 與 Swift 語法對照表(2025 年版) 在行動應用開發中, Kotlin 與 Swift 分別是 Android 與 iOS 的主流語言。雖然語法有些差異,但其實它們有很多相似之處。本文整理了常用的語法對照表,方便跨平台開發者快速上手。 1. 變數宣告 // Kotlin val name: String = "Alice" // 常數 var age: Int = 25 // 可變數 // Swift let name: String = "Alice" // 常數 var age: Int = 25 // 可變數 2. 條件判斷 // Kotlin if (age >= 18) { println("Adult") } else { println("Minor") } // Swift if age >= 18 { print("Adult") } else { print("Minor") } 3. 函式定義 // Kotlin fun greet(name: String): String { return "Hello, $name!" } // Swift func greet(_ name: String) -> String { return "Hello, \(name)!" } 4. 陣列與迴圈 // Kotlin val fruits = listOf("Apple", "Banana", "Cherry") for (fruit in fruits) { println(fruit) } // Swift let fruits = ["Apple", "Banana", "Cherry"] for fruit in fruits { print(f...

[Java] UVa 483 Word Scramble

題目連結 題意: 給定多行字串 每行空格之間為一單字 每個單字要反轉輸出 檔尾結束 EX: 123 456 7890 輸出: 321 654 0987 解法: 一開始我用 split 切割空格 每個單字各自反轉輸出 結果得到 presentation error 因為題目原本多少空格就要輸出多少個 如: 123   45 321   54 就不能這樣讀測資了 後來只好逐個字元判斷 用 stack 讀每個單字 遇到空格就先輸出(清空) stack 再輸出空格 由於機制是遇到空格才輸出 最後迴圈離開後再補一次輸出 stack 程式(Java):

[Java] UVa 10921 Find the Telephone

題目連結 題意: 給定數行測資 每行30個字以內 依題目規定將測資的英文字轉成特定數字 ABC - > 1 DEF - > 2 ... 解法: 沒有特殊技巧 逐字讀取並判斷後輸出即可 測資只會有大寫英文字,  - , 0, 1 不是英文字就直接輸出 程式(Java):

[Java] UVa 382 Perfection

題目連結 題意: 測資只有一行,N個數字 數字間以空格相鄰 每個數字計算其所有因數總和(不含自己) 總和等於自己: PERFECT 小於/大於: DEFICIENT/ABUNDANT 輸出依範例輸出的格式 解法: 主要考你找因數的方法 看測資在60000以下,可以暴力找 找完加總,看情況輸出即可 (1好像歸在DEFICIENT) 程式(Java):

[Java] UVa 11942 Lumberjack Sequencing

題目連結 題意: 每組10個數字 10個數字遞增或遞減,輸出 Ordered 否則輸出 Unordered 解法: 遞增或遞減都輸出 ordered 可以先判斷首二者的關係(遞增或遞減) 後續關係持續遞增或遞減即可 題目沒有提到相同的情況,就不額外考慮 如: 1 1 1 1 2 2 2 2 3 4 程式(Java):

[Java] UVa 11854 Egypt

題目連結 題意: 給定三段長度 判斷是否可形成直角三角形 是,輸出 right 否,輸出 wrong 解法: 先排序後,判斷 兩小邊之平方和是否等於最大邊之平方 程式(Java):

[Java] UVa 1225 Digit Counting

題目連結 題意: 給定 N 計算從1 ~ N,0 ~ 9出現的次數 解法: 一個想太多 範圍在10000以內,暴力求即可 超過10的數就一位一位數分解 程式(Java):

[Java] UVa 621 Secret Research

題目連結 題意: 給定一個數字(沒說會多大) 判斷是4種情況的哪種 + 數字為1 或 4 或 78 - 數字結尾為 35,如: 1935, 77777735 * 數字 9 開頭 4 結尾 ? 數字 190 開頭 解法: 當成字串就好 很簡單的字串比對 題目說無法分析時就輸出第一個符合的 所以依 + - * ? 順序判斷即可 假設測資必符合其中一種 (題目沒說有例外) 如果有用 uDebug,會發現出現不屬於任一種的測資,參考解答卻跑得出結果 可能是他的程式把其中一種 Case 當最後的 else (也就是不屬於其他三者的都會掉到這個else) 程式(Java):

[Java] UVa 686 Goldbach’s Conjecture (II)

題目連結 題意: 給定正整數 n (4~2^15) 求該數為兩質數之和的組合個數 令 n = p1 + p2 求 p1 和 p2 皆為質數的情況有多少? (p1可以等於p2) 如: n = 4 4=2+2(2為質數) 輸出 1 n = 10 10 = 3 + 7 10 = 5 + 5 輸出 2 解法: 先建質數表 檢驗所有p1 和 p2 組合即可 除了  n = 4 以外 其他數不可能有偶數的質數 所以檢驗時可以排除偶數 時間至少省一半 (建質數表也可以只建奇數) 程式(Java):

[Java] UVa 10268 498-bis

題目連結 題意: 計算多項式微分之後的值 每組測資兩行 第一行是 x 的值 第二行是 多項式各項係數 例如: 7 (x = 7) 1 -1 (x-1) x - 1 微分後為 1,不用代入x 答案為 1 2 (x = 2) 1 1 1 (x^2+x+1) 微分後為 2x+1 代入得解為 5 解法: 按微分後的寫法求解即可 須注意本題的測資 數字間不一定只有一個空格 如果只以單空格去切會 Runtime error 例如: 2 1 1   1 以字串讀入後 切開可以寫成: String s = sc.nextLine(); String str[] = s.split("\\s+"); 這是正規表達式的寫法 \\s表示有一個空格 +表示可能為1~多個 符合空格1~多個就切開 範圍會達2^31,要用long 程式(Java):

[Java] UVa 11340 Newspaper

題目連結 題意: 報紙投稿賺稿費 先給 K 個字元與稿費的對照 再給 M 行內容 計算所有內容的稿費總金額 (沒寫的字元以 0 元計算) 測資的稿費單位是分 cent 輸出時要輸出元 dollar 1 元 = 100 分 雖然題目沒說到第幾位 根據下面這行 Examples: ‘3.32$’, ‘13.07$’, ‘71.30$’, ‘0.09$’. 就是輸出到第 2 位吧 解法: 一開始我想的是用 HashMap ASCII 字元不過就 256 個 其實用一維陣列就可 每次清空 0,有提到的字元設值 最後求總值 一開始看似 uDebug都沒問題 提交後出現可怕的 Runtime error 上網查發現問題出在測資 疑似參雜了 ASCII 超過 256 的字元 其他語言的狀況我不了解 後來是在 Scanner 宣告時如下 Scanner sc = new Scanner(System.in,"ISO-8859-1"); 加上 ISO-8859-1,才解決問題 程式(Java):

[Java] UVa 11689 Soda Surpler

圖片
題目連結 題意: 汽水控 有 N 組測資 每組測資如下: 有 e 瓶 空瓶 ,撿到 f 瓶 空瓶 每 c 個空瓶可以換新的一瓶 求可以 喝到 幾瓶汽水 解法: 題目問"喝到幾瓶" e 跟 f 都是空瓶,不能算進去答案 令 own 為當下空瓶數 原始 own = e+f 每次都去除 c,統計數量即可 注意每次換新瓶前 own 要加上上次沒換的 例如: own = 10, c = 2 第一次換了 5 瓶,剩 0 空瓶 此時共喝 5 瓶,own = 5 再來換 5/2 = 2 瓶, 剩 1 空瓶 此時共喝 5+2 = 7 瓶 own 為 2+1 = 3 再來換 3/2 = 1 瓶, 剩 1 空瓶 此時共喝 7+1 = 8 瓶 own 為 1+1 = 2 還可以換 2/2 = 1 瓶,沒有剩下 此時共喝 8+1 = 9 瓶 own 為 1 所以結算下次的 own 時 要去看當次 own/c 能不能整除 如果整除 就是產生 own/c 空瓶 如果不整除,如下例: 會剩下 own - (own/c)*c 下次的 own 就是 own - (own/c)*(c-1) 寫成 own -= (own/c)*(c-1); 程式(Java):

[Java] UVa 13148 A Giveaway

題目連結 題意: 給定一個數 N(1億以內) 如果是一數的平方,也是另一數的次方 輸出 Special 例如: 1, 64, 729, ... 否則,輸出 Ordinary 解法: 題目很好心... 範圍內的結果通通告訴你 用 if else 判斷就可以暴力解決 正常方法就是分別開 2 方與開 3 方 理論上結果都是整數就是 Special 這裡用到的方法是 Math 的 pow(m, n) 可以回傳 m 的 n 次方(double) 開 2 方就是 * 1/2次方 開 3 方就是 * 1/3次方 不過,如果寫成  Math.pow(N, 1/2) 會發現結果是 1 因為直接 1/2 會 = 0 (整數/整數) 任何數的 0 次方為 1 所以要先強制轉型:  Math.pow(N, (float)1/2) 以為這樣就可以了 結果卻發生另一件事 如: Math.pow(64, (double)1/3) = 3.9999999999999996 Math.pow(64, (float)1/3) = 4.000000165259169 Java 的浮點數在計算上產生了極小誤差 反正我們要的是整數 可以用 Math.Round 或其他方式 取最趨近的整數值後逆推回去 看該數的平方或立方是不是原數即可 再者 該數同時為一數的平方,與另一數的次方 則該數必滿足為某數的 6 次方 只要思考質因數分解 假設 N = A ^ 2 = B ^ 3 必然存在 N = (C ^ 2) ^ 3 可以觀察題目提供的數: 1 = 1 ^ 6 64 = 2 ^ 6 729 = 3 ^ 6 4096 = 4 ^ 6 所以只要開 6 次 取整數乘回去 = N 即是解 程式(Java): 目前 GitHub gist 有些狀況 當程式看不見,請參考: https://github.com/maxi67/UVa/blob/master/UVa13148.java

[Java] UVa 151 Power Crisis

題目連結 題意: 能源危機,各個地區要輪流限電 給定 N ,代表有 1~N 個地區 每次都從 1 開始 求最小正整數 m 使得重複每 m 個地區斷電後 最後一個斷電的是地區 13 超過 N 後再從 1 開始 已經斷電的則跳過 例如: N = 13,m = 1 斷電順序 : 1, 2, ..., 13 若 N = 14, m = 2 斷電順序 : 1, 3, 5, 7, 9, 11, 13, ... 斷到 13 後下一個預計是 2 也就是 13 並不是最後斷電 2 就不是答案 解法: 暴力模擬即可 如果 N 限定過大可能就行不通 題目要求最小的 m 就從 1 開始代入 每次從 1 開始,每 m 個一數 數到 13 就看是不是最後一個 m 可能超過 N,例如 N = 14, m = 18 目前不確定該取多少 不過 N 只介於 13 ~ 100 保險一點倒是可以先測測看 (N 代 13~100 最大的 m 為多少) 此外 這題其實是一個特殊題型 叫做 約瑟夫問題 了解的人可以直接套用公式求解 詳情可以參考:  約瑟夫問題(Josephus Problem) 程式(Java):

[Java] UVa 414 Machined Surfaces

圖片
題目連結 題意: 給定 25 * N 範圍的圖 圖上兩邊有字、中間空白 'X' 代表字,'B' 空白(實際上是空白字元) 圖的兩邊要拼在一起 求拼起來後空隙的數量 解法: 討論以下情況 紅橙代表兩邊的X 當 N 只有一行 必然可以完全接合 -------------------------------- 再看以下 各行都含一個空格 可以平移 1 位後完全接合 -------------------------------- 若某一行多一空格 則該空格就會形成空隙 -------------------------------- 再看一個例子 空格數分別為 1, 2, 3, 4, 1 可以平移 1 位 -------------------------------- 也就是說 最多可以平移各行間最小的空格數 剩下的都會形成空隙 總結以上 求出各行之間最少的空格數 計算比它多的各行差值 最後加總就是答案 程式(Java):

[Java] HashMap(Map)可以解的UVa題型

HashMap - Key 與 Value 1. 多組 A 之於 B,給定 A,呼叫 B 10282 Babelfish 11233 Deli Deli 11917 Do Your Own Homework! 2. 給定多個字串,統計個數後依順序輸出 10226 Hardwood Species 10420 List of Conquests 3. HashMap 的 Value 為一個 list,也就是一對多 11991 Easy Problem from Rujia Liu? 一個數字對應多個出現的 index

[Java] UVa 10226 Hardwood Species

題目連結 題意: 每組測資隨機給物種的名字 統計各物種所佔的百分比 以字典序(ASCII大小)順序印出 如: AA AA BB CC 輸出: AA 50.0000 BB 25.0000 CC 25.0000 (單位: %,輸出到小數第 4 位) 解法: 以 HashMap 建立對應的物種與數量 讀到該物種就呼叫(Key) 使數量+1 (value) 不過,HashMap 無法針對 Key 排序 就另外建一個 ArrayList 用 Collections 的 sort 方法排序後 依次從 Map 中叫出數值輸出 因為要算百分比 每次讀測資要順便統計總數 最後用各數量去除 除完之後要 *100 單位才是 % 題目要求看起來繁雜 小心翼翼處理即可 看到網路上有人用 TreeMap 因為會自動排序 就可以省下排序的動作 不過似乎也因不斷動態排序 時間會消耗不少 程式(Java):

[Java] UVa 12405 Scarecrow

題目連結 題意: 有一塊 1 * N 的田 .  表示作物可生長的空地 # 是不可用的 稻草人可以立在任何地方 可照顧它所在與左右各 1 塊的區域 求最少要立多少稻草人 才能保護所有作物可生長空地 解法: 既然所有 . 空地都要被保護 就線性掃過整塊田 遇到 . 就算一隻 而且一隻可以照顧三格 立完後往後跳 3 格繼續掃描即可 程式(Java):

[Java] UVa 10130 SuperSale

題目連結 題意: 一家人逛超市 給定 N 種物品的價格與重量 還有 G 個人各自的負重上限 物品沒有購買數量上限 每個人每種物品只能買一個 求可以買到的物品最大的總價值 如: 3 6 3 8 4 10 5 2 10 12 N=3 / G=2 有 3 件物品(價/重) 2 個人,負重上限為 10, 12 第 1 個人買後兩者(總價最大) 第 2 個人買全部 總價 (8+10) + (6+8+10) = 42 解法: 典型的 0/1 背包問題 (0/1 knapsack problem) 也就是在負重上限前提下 選擇價值最高的物品組合 0/1是指物品只能要或不要 (若沒有 0/1 就是物品可以要 小於 1 份) 觀察題意可以發現 每個人的情況彼此互不影響 也就是各自進行 0/1 背包問題後加總即可 題目規定背包容量上限只有 30 所以可以預先建表(很小) 計算 1 ~ 30 各重量的最大價值 最後直接得解加總 程式(Java):

[Java] UVa 11089 Fi-binary Number

題目連結 題意: Fi-binary number 是指沒有相鄰 1 的二進位數字 由小到大前 10 個為 1, 10, 100, 101, 1000 1001, 1010, 10000, 10001, 10010 給定一個數字 N 輸出第 N 個 Fi-binary number 解法: 這題的關鍵是費氏數列 題目要求的 恰好是 N 的費氏進制 關於費氏位數 第一位為 1 第二位為 2 第三位為 3 第四位為 5 第五位為 8 ... 如: 10 = 8 + 2 = 10010 (fib) 20 = 13 + 5 + 2 = 101010 (fib) 費氏進制分解的做法 可以參考 UVa 948 Fibonaccimal Base 找到最高位元後,往下判斷 fib(i) >= N就補 1,否則補 0 程式(Java):

[Java] UVa 948 Fibonaccimal Base

題目連結 題意: 已知費氏數列: fib(1) = 1 fib(2) = 2 fib(3) = fib(1) + fib(2) = 3 fib(4) = fib(2) + fib(3) = 5 ... 給定數字 N 分解成費氏數列的組成(費氏進制) 如: 17 = 13 + 3 + 1 寫成 100101 (13,8,5,3,2,1) 解法: 注意輸出是由高位元到低位元 先求出範圍內最大的費氏 此處 N 可以到 1 億,大概是 fib(43) 然後從最大的判斷回來 若 fib(i) <= N,就是最高位元的 1 令 N = N - fib(i) 後繼續做 fib(i) <= N 補 1 fib(i) > N要補 0 程式(Java):

[Java] 字串串接比較 concat & StringBuilder

在 Java 當中,有很多字串串接的方法 最簡單的就是直接用 + 串起來 如: String S1 = "A" + "B"; 也可以用 concat 方法 如: String S2 = S1.concat("C"); 或是透過 StringBuilder 如: StringBuilder sb = new StringBuilder("A"); sb.append("B"); 以下分別測試從 1 串接到 k 的執行效率 (以執行時間做區別)  String 是固定長度的型別 更改長度就是 new 新對象的概念 會消耗許多資源 相比之下,StringBuilder 就像一個容器 可以輕易地將字串增長或減短 也是在針對同一個對象 因此在 k 值愈大的時候 方法之間的執行效率顯而易見 而 String 與 StringBuilder 轉換也很容易 String -> StringBuilder: 宣告一個物件,參數放字串 StringBuilder sb = new StringBuilder("A"); StringBuilder -> String: 用 toString 方法 System.out,println(sb.tostring()); 參考資料: 1.  Charles的崩潰人生: Java String、StringBuffer、StringBuilder的差別 2.  String、StringBuilder與StringBuffer 的差別@ 愛迪生的異想世界:: 痞客邦::

[Java] UVa 1062 Containers

題目連結 題意: 只知道跟船阿貨運有關係XD 題目給定一個 A ~ Z 組成的序列 (由小到大) 輸出該序列的最長遞增子序列 (LIS) 的長度 舉例: ABAADEF LIS 為 ABDEF,輸出 5 LIS 不一定要是連續的 而且為嚴格遞增 也就是任意前必小於後 (不能有重複) 像題目的 CBACBACBACBACBA LIS 為 ABC,輸出 3 不能為 AABC 或 ABBC 之類的 解法: 用一個陣列 LIS[ ] 紀錄以某元素為結尾的 LIS 長度 由前而後 Greedy 掃一遍即可 舉例: ABADEF,預設都是 1 以 B 為準,往前掃到 A 可以接在 A後面 B 的 LIS 就可以是 A 的 +1 不過若 B 本來就比較大,就不更動 程式(Java):

[Java] UVa 10235 Simply Emirp

題目連結 題意: 測資給一個100萬以內的數 N 如果它是質數 而且它的反轉也是質數 輸出 N is emirp. 如: 17,17 和 71 都是質數 如果它是但反轉不是 輸出 N is prime. 如: 23,23 是但 32 不是 如果它不是 輸出 N is not prime. 如: 18, 18不是質數 解法: 先建一個 1000000 以內的質數表 判斷它與它反轉是不是質數即可 如果它本身反轉還是自己 如果是質數,要輸出 N is prime. 程式(Java):

[Java] UVa 10815 Andy’s First Dictionary

題目連結 題意: 給定好幾行字 找出單字(只由連續字母組成) 以字典序輸出所有單字(以全小寫字母) 解法: 因為解答要求小寫 先將讀入的字串轉小寫 找出單字的作法頗多 我是先逐字判斷 不是字母就通通以空白代替 最後用 split 方法切開 然後一一存到 ArrayList 重複的要跳過 接著可以用 Collections 的 sort 方法排序 最後依序輸出即可 切的過程發現 可能有連續 2 個不是字母 所以會冒出一個空字串 反正也只會存一次(重複已跳過) 排序時也會排到最前面 輸出時 index 從1開始就可以避開 另外這題是讀到檔尾 測資也不是以行為單位輸出 想要用 Console 視窗測試可以試試: 在 while 迴圈讀到字串後 加下面幾行 if (s.length()> 0) if(s.charAt(0)=='2') break; 測試時打個 2 就可以跳出迴圈了 記得丟 UVa 要槓掉XD 程式(Java):

[Java] UVa 272 TEX Quotes

題目連結 題意: 題目會給好幾行測資 其中包含偶數個雙引號 " 字元 測資輸入什麼就輸出什麼 除了 遇到第單數個雙引號 要輸出 `` 遇到第雙數個雙引號 要輸出'' (兩個單引號) 解法: 不需要特別的解法 可以用一個布林變數 紀錄現在是單數個或雙數個 照著規定輸出就可以了 程式(Java):

[Java] UVa 145 Gondwanaland Telecom

題目連結 題意: 電話費計算程式 有 5 種地區 A, B, C, D, E 還有分三種時段,費率各不相同 測資每行一組 分別給地區, 電話號碼, H1, M1, H2, M2 後 4 個數字代表時間區間,從 H1:M1 ~ H2:M2 計算該區間內的電話費 輸出要照格式依序輸出 前10位靠右對齊輸出電話號碼、 三個時段佔的分鐘數(各6位)、 地區(3位)、 電話費(8位) 解法: 很直觀,也很麻煩 先建地區對應時間的表 給定一個區間,如何個別統計 3 個時段佔多少呢? 這邊只是提供我的土法,一定有更快的 開一個一維陣列,表示所有分鐘 先判斷時間區間前者晚於或早於後者 如果前者較晚,表示有跨日 例如 3:00~5:00 就是同一天,共2小時 5:00~3:00 就是跨日,共22小時 題目有說區間不超過24小時 所以不用做其他判斷 (如果時間相同,如 8:00~8:00,表示跨日,經過一天) 然後按區間經過的,就在陣列註記 最後三個時間各自統計範圍內註記的總分鐘數即可 記得輸出照位數輸出 可以用跟 C 語言相同的 printf 方法 細節就不詳述 程式(Java):

[Java] UVa 10114 Loansome Car Buyer

題目連結 題意: 這題光理解題意就費了很一番功夫= = 以輸入測資來講 每組測資第一行 mon, down, loan, d 假設你有 down 元,用它加上貸款 loan 買了一部車 車子價值 down + loan 貸款 loan 分 mon 個月 0 利率償還 而車子會每年減值(depreciation) 接下來的 d 行測資是減值資訊 每行 tmp, val 表示第 tmp 個月車子價值會掉 val 也就是變成本來的 (1 - val) 每組測資都會有第 0 個月,表示一開始就會減值 沒提到的月份就跟前一個月一樣 計算哪個月開始,車子的價值會高過貸款 loan 解法: 在一個迴圈內,直到貸款還完的月份 個別計算每個月剩餘貸款與車子價值 貸款就每個月扣 loan / mon 車子價值則是每個月先讀 val 拿車子當前價值 *(1-val) 兩兩比較即可 輸出時只有一個月 month 不加 s,其他都要 程式(Java):

[Java] UVa 10550 Combination Lock

圖片
題目連結 題意: 3 道密碼的密碼鎖 算解開的過程共轉多少角度(1圈360) 如上圖,倒三角形是指針的位置 轉中間的圓圈,會連整個刻度盤轉動 假設本來是 0 度,要轉到現在約 38 度 圓圈是如圖中順時針轉,刻度才會逆時針 所以題目敘述的方向要反向思考 題目給定一開始的位置,還有 3 個密碼 a, b, c 1. 順轉 2 圈 2. 順轉到密碼 a 3. 逆轉 1 圈 4. 逆轉到密碼 b 5. 順轉到密碼 c 解法: 基本上看懂題意,能用範例輸出推得,這題就OK了 照上面 5 個步驟累加即可 指針共有 40,角度有 360 可以先求指針變化量,最後 *9 得解 程式(Java):

[Java] UVa 12289 One-Two-Three

題目連結 題意: 弟弟學寫字 給定字串,可能代表 one, two, three 但會包含最多一個錯字 如:  one - > oqe, two - > twv 輸出其代表的數字 解法: 因為只會有 3 種可能,想辦法區別即可 例如 只有 3 有 5 個字元,先分開 1 跟 2 就拿其中一個的正解來逐個字元比對 因為最多只會錯一個 所以正確字元 >= 2 就正解,否則為另一個 程式(Java):

[Java] UVa 10346 Peter’s Smokes

題目連結 題意: Peter 有 n 支菸 每抽完 k 支菸會捲成新的一支繼續抽 給定 n, k,求他可以抽幾支? 解法: 以 n = 58, k = 15為例 先 n/k = 3 得知他原本抽 58 支後 可以拿抽過的其中 45 支捲成新的 3 支 要注意,他還有 58-15*3=13 支抽過的 當新的 3 支抽完後 共有 13 + 3 抽過的,可以再捲一支 因此總共抽了 58+3+1 = 62 支 只要一直判斷抽完的會不會再湊到 k 即可 程式(Java):

[Java] UVa 10189 Minesweeper

題目連結 題意: 踩地雷,測資會給 n*m 的矩陣 *代表地雷,.代表沒事 輸出時也是輸出矩陣 地雷就輸出* 沒事的要輸出自己四面八方的地雷總數 解法: 我的寫法比較土法煉鋼 或許能更快更精簡 寫一個函數,判斷每一格周圍的地雷數 參數是當下的座標,依序判斷八個方位就對了 程式(Java):

[Java] UVa 11332 Summing Digits

題目連結 題意: 題目定義了2個函數:  f(x) 計算正整數 n 的各個位數總和  g(x) 遞迴執行 f(x) 直到 f(x)的結果為個位數 簡言之 先計算給定 n 的各位數之和 若結果為二位數以上 (>10),則重複動作 解法: 按照思維 先寫出 f(x) 的函數 也就是可以執行一次計算各位數之和 再接著主程式裡寫 while loop 遞迴跑 等結果 < 10 才會離開迴圈 程式(Java):

[Java] UVa 10100 Longest Match

題目連結 題意: 每組測資給兩行字串 比較兩字串依順序出現相同的單字數最多有多少 所謂的單字是指由英文字母或數字組成 例如: 777 888 99a.25 以上有 4 個單字, (.非有效,99a 和 25 是兩個單字) 也就是最長共同子序列問題 Longest Common Subsequence (LCS) 只是元素從單個字元變成單字 解法: 如果以字元為單位 還要先分析哪裡到哪裡是有效單字 實作起來會很費力 所以乾脆先處理輸入測資,找出單字 用字串陣列 String[ ] 存每個單字 題目就真的能以 LCS 問題來解了 找出單字時,先將字串整理 非字母與數字的一律以空格取代 再用 split 方法切開,陣列就幫你存好材料了 解 LCS 時,判斷單字相同用 equals 方法比較 然後用 DP 找最大解 ff[i][j] 表示字串 1 到 i,字串 2 到 j 的位置當下的 LCS 長度 程式(Java):

[Java] UVa 490 Rotating Sentences

題目連結 題意: 測資只有一組 給定好幾行字串 整段文字順時針90度後輸出 解法: 用二維陣列存 index 設計一下輸出即可 字串長短不一時,要記得補空格 程式(Java):

[Java] UVa 10424 Love Calculator

題目連結 題意: 給兩字串 不管大小寫,依照 A = 1, B = 2, ..., Z = 26 加總 分別計算兩字串的分數 若分數超過 2 位數,將各位數字加總,直到結果為 1 位數 如: 77 = > 7+7= 14 = > 1+4 = 5 求兩字串比值,不得超過 100% (大的當分母) 解法: 直觀的題目,依照規則寫即可 1. 注意測資可能亂七八糟 可以先轉成小寫 (ToLowerCase,只統計小寫字母) 2. 要判斷兩分數大小,而且要依百分比格式輸出 相等沒差,反正都是 100% 3. 若算分數是用整數變數存,計算比值要先強制轉型 直接用整數相除會無條件捨棄小數 (如: 5/3 = 1) 程式(Java):

[Java] UVa 10489 Boxes of Chocolates

題目連結 題意: Little Pippy 有超多巧克力,她想平分給好朋友 要幫她計算最後分不完的數量 每組測資第一行先給 N, B 前者是好朋友人數,後者是巧克力盒數 接著 B 行各自給 K 與 a1, a2, ..., ak 表示每盒裡有 a1 小盒,每小盒裡又有 a2 小小盒... 最後求分給 N 個小朋友後剩多少無法平分 例如: 4 2 3 2 3 4 2 6 3 表示這組有 4 個朋友,2 盒巧克力 第 1 盒有 2 小盒,每小盒有 3 小小盒,每小小盒有 4 個巧克力 第 2 盒有 6 小盒,每小盒有 3 個巧克力 總共有 4*3*2 + 3*6 = 42 個巧克力 分給 4 個小朋友後,剩 2 個(除以 4 餘 2) 解法: 題目規定T, B, K 可以達到 100 ai上限可達10000,即最多可連乘 100 次 10000 所以全部相乘相加會爆掉 Java 用大數乘法可以AC 另外一解是用餘數的特性 (參考自 演算法筆記 ) 我們把求 7 除以 5 的餘數記成以下: 7 mod 5 ≡ 2,其中 5 稱為模數 當模數相同時,餘數可以相加、相乘 如: (7 mod 5) + (11 mod 5) ≡ (18 mod 5) < (2+11) mod 5 ≡ 3 / 18 mod 5 ≡ 3 >(相加結果相同) (2 mod 5) * (3 mod 5) * (4 mod 5) ≡ (24 mod 5) < (2*3) mod 5 ≡ 1, (1*4) mod 5 ≡ 4 / 24 mod 5 ≡ 4 >(相乘結果相同) 以上相乘恰滿足題意提到的第一個盒子 因此,原本的作法是各自相乘後相加再 mod 可以變成各自 mod後再乘,mod 後再相加,最後再 mod 就是結果 參考資料: 演算法筆記 - Residue:  http://www.csie.ntnu.edu.tw/~u91029/Residue.html 程式(Java):

[Java] UVa 10926 How Many Dependencies?

題目連結 題意: 有若干個 Task 彼此間有相依關係,分成直接與間接 如: A depends on B, and B depends on C 則可以說 A 有 2 個依賴,B 1個,C 0 個 (單向,A 對 B不能算給 B) 要找出依賴最高的 Task 每組測資有 N 個 Task (編號 1 ~ N) 題目會依序告知 N 個 Task 依賴的 Task 們 例如: 3 1 2 1 3 第 1 行表示有 3 個點 第 2 行為 Task 1 1 表示有 1 直接依賴到 Task 2 第 3 行為 Task 2 1 表示有 1 直接依賴到 Task 3 第 4 行為 Task 3 0 表示沒有依賴 最後輸出最高依賴的編號 如上例輸出 1 (Task 1 有 2 依賴最高) 解法: 當作圖論解 單向圖,以 DFS 或 BFS 走訪計算最大值 題目有說測資不會出現 cycle 也就是若 A 依賴 B,B 不可能依賴 A 所以單純找單向的直接與間接依賴即可 程式(Java):

[Java] UVa 11917 Do Your Own Homework!

題目連結 題意: Soha 都叫 Sparrow 幫他寫作業 題目會告訴你 Sparrow 有哪些擅長科目 以及 Soha 有哪個科目的作業要做 每組測資先給 N 個科目與對應天數 代表 Sparrow 擅長的科目,以及分別完成時間 然後是作業科目(每組只有一個)與期限天數 D 如果作業是 Sparrow 擅長的 也能 D 天內完成,輸出 Yesss 如果擅長且能在 D+5 天內,輸出 Late 如果超過 D+5,或不是擅長的 輸出 Do your own homework! 解法: 先用 Structure, 陣列或 Map 等等 能同時存 2 種型別的資料結構 紀錄擅長科目與天數 接著搜尋作業是否存在資料內 有則抓出天數,與 D 比較 最後輸出對應結果 以下以 HashMap 為例 程式(Java):

[Java] UVa 10591 Happy Number

題目連結 題意: 給定一個數字 循環的計算該數字每個位數的平方之和 若最後結果為1,該數字為Happy Number 若否,則為Unhappy number 例如: 7 7^2 = 49 4^2 + 9^2 = 97 9^2 + 7^2 = 130 1^2 + 3^2 + 0^2 = 10 1^2 + 0^2 = 1 7為 Happy number  解法: 用一個Set存出現過的值 照上面的作法運算 每次結果判斷是否存在set 若否就繼續做到結果 當結果為1 ,輸出Happy number 若出現過,表示後續會一直重複 找不到最後為1的情況 輸出Unhappy Number 程式(Java):

[Java] UVa 10101 Bangla Numbers

題目連結 題意: 一個十進位的單位唸法轉換 像我們一般說 6958為 6 千 9 百 5 十 8 這些千、百、十分別代表1000, 100, 10 給定一個數字(最大到十進位的15個9) 按照題目要求的單位輸出對應唸法 題目的單位如下: ’kuti’ (10000000) <8位數> ’lakh’ (100000) <6位數> ’hajar’ (1000) <4位數> ’shata’ (100) <3位數> 例如: 23764 =  23 hajar 7 shata 64 因為範圍可能到15位數 超過kuti的要重複編 像是: 4589745 8973958 = 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58 解法: 因為每7位數一個循環判斷 可以寫一個函式遞迴跑 遇到大於7位,輸出 kuti後 再執行函式,參數放除以10^7後的數 其他幾個單位也可以用相同方式 輸出對應文字後 以除後的數當參數再跑函式即可 須注意,每個數字輸出之前 題目要求要先輸出是第幾個數字 如第一個:  1. 格式是4個字元靠右 可以用printf的%4d表示 另外,百位以下如果是0,如200 0不必輸出,也就是 2 shata 但如果輸入本身是0,又必須輸出 0 這點要想辦法判斷 程式(Java):

[Java] UVa 10098 Generating Fast, Sorted Permutation

題目連結 題意: 每組測資給定一個字串(長度最多10),要按順序列出所有相異的 Permutation 所謂的 permutation 指的是某個字串的一種排序方式 組成相同,但順序不同 例如: 字串 ABC,他的 permutation 有: ABC, ACB, BAC, BCA, CAB, CBA 總共會有3! (3階乘) = 6種 題目要求按照字母順序從頭到尾輸出 像是給定 BCA ,其 permutation 與上述的ABC相同 輸出如下: ABC ACB BAC BCA CAB CBA 解法: 解題關鍵就是要找到所有permutation 而且必須是按字母順序 在C++的STL當中 似乎有相關方法可以呼叫(next_permutation) 不過Java沒有 所以我們必須自行實作 觀察找出下一個 permutation 的規律 規律如下: 以ABCDE為例,原本字串是遞增的 (以ASCII來看) 我們的最終目標是遞減的EDCBA (也就是最後一個 permutation) 下面列出前幾個 permutation : ABCDE - ABCED - ABDCE - ABDEC - ABECD - ABEDC - ACBDE - ... 首先思考一下,我們寫一個字串的時候 第一個位置有5個選擇,第二個位置有4個,依此類推... 加上要按順序寫,所以第一個permutation產生的理由是 第一個位置可以選A~E,選擇最前面的A 第二個位置可以選B~E,同理 最後得到ABCDE 第二個permutation,由於第五個位置已經沒得選了 回到第四個位置,原本可以選D~E,現在選擇E,最後還是只能選D 所以得到ABCED 再者,第四個位置DE都選過了 所以往前到第三個位置,選擇C的下一個順位 D D選完後,第四個位置可以選CE,選擇C,最後E 所以得到ABDCE 依此類推... 過程中 連續選過的位置會形成遞減的情況 往前找到沒有遞減的字元 取得該字元下一個順位後 後面的字元再形成他們自己的第一個 permutation 也就是字元由小到大排序的結果 最後就得到該次 permutation [程式實作] 每次從後往前檢查兩兩相鄰字元 ...

[Java] UVa 10009 All Roads Lead Where

圖片
題目連結 題意: 有若干城市,城市之間可能存在連線 每組測資先給定m,n 代表有 m 組程式間的連線 接著問 n 組,從某地到另一地可能的最短路徑 針對n行問題,每行輸出最短路徑的每個城市第一個字母 例如: 3 1 Aa Bb Aa Cc Cc Dd Aa Dd 如上,m = 3,n = 1 Aa和Bb,Aa和Cc,還有Cc和Dd之間有連線 然後問Aa到Dd可以怎麼走 最短路徑為 Aa-Cc-Dd,輸出ACD 解法: 先透過HashMap建立連線 Key - Value 代表可以從城市 Key 到城市 Value 因為連線是雙向的 所以當input為A B時 要分別以A為Key加B Value,以B為Key加A Value 此外,因為一個城市可能可以同時連到多個其他城市 Value可以用ArrayList<> (等於一個key對應多個Value) 然後,實作上可以用BFS 先建立另一個HashMap(prev) 紀錄路徑 也就是以S為起點時,有沒有其他城市(Value)可以走到特定城市(Key) 所以一開始會輸入 prev.put(S, null); //S是起點 每次讀取S和D (出發和目的地) 先讀S,判斷可以走到哪些城市(也就是BFS的第一層search) 若城市的prev不存在(表示BFS還沒掃過),就紀錄到prev 當掃到D,就透過prev回朔到S 可以建立一個反轉的字串,最後輸出即可 程式(Java):

[Java] UVa 10008 What’s Cryptanalysis?

題目連結 題意: 要統計所有英文字母的出現個數(大小寫視為一樣的) 由個數多至少列出(每行輸出大寫字母與個數) 若相同則按A~Z的順序 本題只會有一組測資 測資先給行數,依序是每行的若干字元 解法: 由於大小寫需看成相同的 我們先將題目所有字元轉成大寫(ToUpperCase()) 開一個陣列來統計各字母的出現次數 有點偷懶的地方是 可以用字母的ASCII當陣列的索引(index) 如 15 行 讀到 A~Z 的範圍後,假設是 A 16 行 直接在陣列的 c['A'] 加1 (也就是 c[65]) 第6行宣告陣列大小只要比 'Z' 還大就好 (當然陣列大小也可以只有26,記得字元轉換數字index要扣 'A') 輸出時,因為題目要求依個數大到小順序 個數至多就是測資的總字元數吧 (如題目是 30個 A,就只會輸出 A 30,不會超過) 所以在20行,從個數 len 開始 讀到某個數值就按 A~Z的順序去跑 就可以題目要求的方式輸出了 程式(Java):

[Java] UVa 1730 Sum of MSLCM

圖片
題目連結 題意: maximum sum LCM(MSLCM): 找到一個集合,最小公倍數(LCM)為N且該集合的和為最大 舉例: MSLCM(2) = 3: LCM(1, 2) = 2 且 1+2=3為 最大的和 題目給定 N (1<N<20000001) (2千萬) 要求MSLCM(2) ~ MSLCM(N)的和 如: N = 10 LCM(1, 2) = 2, 1+2=3 LCM(1, 3) = 3, 1+3=4 LCM(1, 2, 4) = 4, 1+2+4=7 LCM(1, 5) = 5, 1+5=6 LCM(1, 2, 3, 6) = 6, 1+2+3+6=12 LCM(1, 7) = 7, 1+7=8 LCM(1, 2, 4, 8) = 8, 1+2+4+8=15 LCM(1, 3, 9) = 9, 1+3+9=13 LCM(1, 2, 5, 10) = 10, 1+2+5+10=18 Total = 3+4+7+6+12+8+15+13+18 = 86 解法: 觀察上述例子,會發現 集合的總和為最大,恰為 N 之所有因數形成的集合 但不太可能從 2 ~ N 一一找因數還加總 我們發現,也把MSLCM(1)算進去的話 從1~N(這裡N=10)的所有因數出現次數統計如下: 1:10次  2:5次  3:3次  4~5:2次  6~10:1次 次數恰為 (N/因數) 的值(小數無條件捨去,即程式語言的整數相除) 所以原本的題目可以這樣解: 從2~N依序代入上述關係求得並加總 本來以為這樣就節省很多時間了 但N可以到20000000,所以O(n)還是TLE了 我們進一步發現 這些因數從小到大,出現次數會遞減 而且連續因數的次數可能都一樣(像上述的4, 5都是2次,6~10都是1次) 所以我們希望,次數相同的因數一起算 此時用到類似binary search的做法 得到每個次數的起始與結束區間(左右區間) 把區間內的因數加總後,再乘上次數 以N = 10為例 每次先用前一次結果得到左區間,初始為0,先得到第2列的左=1 剛剛知道因數對應次數可以 (N/因數)得到,所以第2列的次數 t = 10/1 再來...

[Java] UVa 118 Mutant Flatworld Explorers

題目連結 題意: 一個長方形網格,座標左下為(0, 0),右上為(x, y) 有好幾隻機器人,對應題目好幾組指令 每組先給定機器人的原始座標(rx, ry)與面向方位(北N 東E 南S 西W) 接著一連串的指令,包含: R-向右轉 L-向左轉 F-向前走,不轉向 如果機器人因為向前走超出邊界 要輸出最後所在座標、方位與"LOST"並停止該次動作 否則輸出所有指令跑完後的最後所在座標、方位 同一個測資當中,若前次機器人在某個座標LOST 會存在記憶點,也就是之後的機器人在相同位置 如果即將LOST,可以免於一死 舉例來說,假設 3*3的方格 有連續2組測資如下: 1 3 E FFFFF 2 3 E FFFFF 第一個機器人座標 (1, 3),面向東方 指令FFF...,走到 3 3 E後再執行 F 發生 LOST,所以輸出 3 3 E LOST 第二個機器人座標 (2, 3),面向東方 指令FFF...,走到 3 3 E後再執行 F 本來發生 LOST 因為有記憶點,所以可以忽略該F,繼續後續指令 最後輸出 3 3 E (因本例都是F,最後都忽略) 解法: 看似方位又一堆規則顯得複雜 其實照著題意模擬即可 唯一要注意的就是記憶點問題 模擬要記錄三個要素,機器人的x y座標(rx ry)和方位 指令L R只要改變方位 指令F就按照當下方位對座標加減: N ry++ S ry-- E rx++ W rx-- 記憶點的話,建立座標對應的布林陣列 當機器人即將發生LOST,註記當下座標 之後遇到LOST但有註記的座標就忽略 題目看起來只有一組測資 也就是同一個 x * y 網格,多個機器人 程式(Java):

[Java] UVa 11541 Decoding

題目連結 題意: 一個解碼的概念 每組測資以數個 (字母 + 個數) 的組合而成 照規則輸出即可 如: 輸入 A3B5C4 輸出 AAABBBBBCCCC 解法: 這題題目很直觀 比較要思考的是測資的讀法 因為數字不一定只有一位 (EX: A12B2D333) 所以除了紀錄字母外 也要能判斷代表數字的範圍 (如果用 String 讀測資,就得紀錄數字的頭尾 index) 程式(Java):

[Java] UVa 10791 Minimum Sum LCM

題目連結 題意: 給定一個數 N N 可以表示成至少 2 個數的最小公倍數 (LCM) 求那些數最小總和為多少? 如: N = 12 下列組合的 LCM都是 12 (1, 12), (3, 4), (12, 12), (1, 2, 3, 4), ... 其中最小總和為 3+4 = 7 解法: 先將 N 進行質因數分解 然後把相同質因數相乘得到某些數 也就是所有質因數的最高次 (仍是N的因數) 例如: 12 = 2*2*3 = 4*3  360 = 2*2*2*3*3*5 = 8*9*5 可以觀察到, N 可以表示成這些數的乘積 他們不但彼此互質(符合 LCM 為 N 的特性) 總和也會最小 因此,只要質因數分解 當找到質因數,就持續分解得該質因數的最高次數 最後求這些數總和即可 程式(Java):

[Java] UVa 10626 Buying Coke

題目連結 題意: 一瓶可樂 $8 每組題目給定要買幾瓶、1元、5元、10元硬幣數量 每次只能買一瓶,找錢會以最少的硬幣數量 求使用最少硬幣的買法,輸出使用硬幣總數 例如: 2 2 1 1 表示要買 2 瓶、$1, $5, $10 分別有 2, 1, 1 個 我們知道,用最少的買法就是花 1 個 $10 所以用 $10 買了一瓶後,會找 2 個 $1 此時硬幣數分別為 4, 1, 0 還有一瓶,只能用 $5 *1  + $1 *3 (4 個硬幣) 所以總共使用 1 + 4 = 5 個硬幣 解法: 以陣列[n1][n5][n10] 表示 在硬幣數分別為n1, n5, n10 時 可以用來買飲料的最少硬幣數 分析任何可以買飲料的硬幣組合(括號表示使用硬幣數): 1. $10 (1) /找 $1 * 2 2. $10 + $1 * 3 (4) /找 $5 * 1 3. $5 * 2 (2) /找 $1 * 2 4. $5 * 1 + $1 * 3 (4) 5. $1 * 8 (8) 飲料一次只買一瓶 寫一個 dp,每次執行代表買一瓶 上述情況都比過一輪判斷最小情況 每次買完會找錢,陣列要開得比測資範圍大 另外注意每組測資前陣列值要初始化 程式(Java):

[Java] UVa 10041 Vito’s family

圖片
題目連結 題意: Vito 有很多家庭成員,他希望能經常拜訪所有人 所以要在與其他人平均相距最短的地方 題目每組先告知有幾個成員 接著給定他們的直線座標 幫 Vito 選擇一個地點,並輸出與其他成員的距離總和 即若 Vito 座標為 S,成員們為 s1, s2, ... 求最小的 |S - s1| + |S - s2| + ... 解法: 求一點距離某些點的總和最小 該點會出現在這些點的中位數 而不是平均數或其他值 可以舉簡單的例子得證 ----------------------------- 假設s1 = 1, s2 = 10, s3 = 10000 若為中位數,Vito = s2 = 10 距離 = 9 + 0 + 9990 = 9999 若為平均數,Vito = (1 + 10 + 10000)/3 = 3337 距離 = 3336 + 3327 + 6663 > 9999 ----------------------------- 此外,若有偶數個點,Vito 可為中間兩數任一點 如: 若 Vito 為 s2 距離為: a + 0 + b + (b+c) 若 Vito 為 s3 距離為: (a+b) + b + 0 + c 結果相同 因為此題輸出整數 否則要取中間兩數的平均值當作中位數,才能得到最短距離 程式(Java):

[Java] UVa 11636 Hello World!

圖片
題目連結 題意: 在 C 語言中,要印出一行 Hello World! 需要執行一行printf("Hello World!\n"); 假設不透過迴圈的方式 要印出1行以上,就只能寫同樣數量的指令 而且只能由原本的指令複製貼上 題目每行代表一組測資 給定要印出的總行數 N,輸出所需最少"複製貼上"的次數(複製貼上算一個步驟) 例: 要 2 行,原本 1 行,複製貼上那 1 行 = 2,共貼上 1 次 要 4 行,用前一例的 2 行都複製貼上 = 4 ,共貼上 2 次 要 5 行,前一例再複製貼上任一行 = 5 ,共貼上 3 次 解法: 因為題目要求要貼上最少次 先判斷每次貼上最多可以產生多少行 (當下的全部複製) 由於都必須由 1 行開始 第 1 次複製得到 2 行 第 2 次複製 全部 得到共 4 行 第 3 次複製 全部 得到共 8 行 依此類推,2 的 n 次方行數最少就需 n 次複製 3 行可以在第2次複製1行時得到 5, 6, 7 行在第3次複製時同理 因此,建立 2 的指數陣列 將題目的總行數 N 依序比,當 N 比陣列值小 該 index 就是對應的貼上數 如 N = 5,5 < 8 index 3 就是輸出值 程式(Java):

[Java] UVa 10013 Super long sums

圖片
題目連結 題意: 計算兩數之和,每組測資一行相隔 先給定兩數之位數 M (同位) 接著每行依序從最高位給兩數的值 題目有說可以是不同位的數 M 會是高位的位數 較低位者的高位會補 0 例如: 931 + 85 3 9 0 3 8 1 5 其中 M 的大小可能達1000000 (100萬位) 解法: 由於M ≤ 1000000 不能當成2個數字直接相加 就算用 BigInteger 也可能無法計算這麼多位的加法 只能建立陣列,計算每個位數的值 先將位數的值個別相加 再處理進位問題,從個位推到最高位 以931+85為例,以陣列大小比題目的位數多 1 做預留 (任兩個 N 位的數相加不會超過 N+1 位) 第一步,各位數相加後,分別存 9 11 6 從個位數開始,十位超過 10,進一位 百位也是相同做法 最後從陣列頭輸出到陣列尾即可 程式(Java):

[Java] UVa 10107 What is the Median?

圖片
題目連結 題意: 只有一組測資 每行輸入一個數字,形成越來越長的數列 每輸入一個數,就要輸出當前數列的中位數(排序後) 當數列長度為奇數,如5,輸出第3個數字 當數列長度為偶數,如6,輸出中間2數的平均,即第3, 4個的平均 當數字不為整數,輸出其整數部分 數字小於10000個,數字大小可能達2^31-1 解法: 如果每次輸入新的數就重新排列再找中位數,一定TLE 因此,必須在輸入時就按小到大的順序,將其放到合適位置 再將該 index 後面的元素都後移一位,可大幅縮短時間 如下,新增 5 之後 5 會從 1 開始比,直到發現比 6 小 5 擺在 6 的位置,6 ~ 9 往後移一位 然後,再從新數列找中位數即可 程式(Java):

[Java] UVa 11634 Generate random numbers

圖片
題目連結 題意: 一個4位數字的亂數產生器 給定一個初始值 a0 產生的方法是先平方,將結果補齊到8位數字 取中間的4位即為新產生的數字 重複動作,計算總共可以產生多少不同的數字 例如: 解法: 重複執行上述動作,每找到新的數字就令次數 +1 用一個陣列表示數字找到與否,若已經找過則停止 因為同一個輸入,必會產生相同的新數字 (都是平方取中間) 題目要計算多少不同的數字 已經找過則表示後續會形成循環,而不必做下去 程式(Java):

[Java] UVa 11455 Behold My Quadrangle

圖片
題目連結 題意: 每組測資給定4段長度,判斷可以組成哪種形狀 square(正方形): 4邊等長 rectangle(長方形): 2邊等長,另2邊也等長 quadrangle(四邊形): 不符合以上情況,但任3邊之和大於等於第4邊 banana 不符合以上條件的其餘情況 可以發現 square 也屬於 rectangle (符合長方形條件) rectangle 也屬於 quadrangle (符合四邊形條件) 以下同理,關係大致如下: 解法: 依序判斷即可,先將4段長度排序 square 可以取最長跟最短比較 因為排序過,若該2者等長,則4段都等長 rectangle 取前 2 者與後 2 者判斷 quadrangle 就抓前3者的和與最長的判斷 (若成立,其他的組合也一定成立) 若都不符合,則為 banana  (反正就什麼都不是....) 程式(Java):

[Java] UVa 11461 Square Numbers

題目連結 題意: 每組測資給定一個區間 a, b(0 < a ≤ b ≤ 100000) 求介於 a ~ b 範圍間的 square number (平方數) 個數 也就是1, 4, 9, 16, 25,... 解法: 因為平方數是已知的 而且只需要求區間內的數量 加上測資範圍不大(最大為10萬) 可以先得到 10 萬以內的所有平方數 ( 1, 4, 9 ...) 然後各自求 a, b 在陣列的對應平方數索引 (  大於 a 的最小平方數  與  小於 b 的最大平方數  ) 兩者索引差就是區間內平方數個數 程式(Java):

[Java] UVa 11417 GCD

題目連結 題意: 給定 N 值( 1 < N < 501) 求 1 ~ N 之間任兩數(i, j)的 GCD (最大公因數)總和 G 其中 1 ≦ i < j ≦ N 若 N 為 3 G = GCD(1, 2) + GCD(1, 3) + GCD(2, 3) 解法: 題目上不但有題意 甚至連程式碼都給了 只需額外撰寫 GCD 的求法即可 GCD的實作大多是透過輾轉相除法 即重複執行大者減小者 1. 當其中一方結果為1,代表互質 2. 當其中一方結果為0,則另一方為GCD  %運算(取餘數)恰好符合這種運作 前者無限次扣掉後者,直到小於後者的值 如 5%2 = 5-2-2=1 / 14%9 = 14-9 = 5 我們遞迴執行取餘數,如 GCD(a,b) = GCD(b, a%b) 每次的 b 代入成新的 a 新的 b 則為 a%b,也就是上一輪的結果 當一方為0時停止,另一方會為 1 或 GCD 例如: (以遞迴GCD的 a, b表示) (14, 9) -  (9, 5) - (5, 4) - (4, 1) - (1, 0) 則互質 (18, 12) - (12, 6) - (6, 0) 則 GCD = 6 程式(Java):

[Java] UVa 11727 Cost Cutting

題目連結 題意: 一間公司決定裁員,對象是最高薪與最低薪者 每組測資給三個員工的薪水,求沒被裁員者的薪水 解法: 找中位數即可 每組只有三個數字,資料範圍也很小(1000~10000) 可以判斷中間值的做法都可以 程式(Java):

[Java] substring 的參數: beginIndex 和 endIndex 的理解

在 Java 的某些方法中,我們會注意到參數會需要代入頭尾的 index 舉例來說 String類別的 substring 方法,可以回傳某字串的子字串 其中一種多載(Overloading)形式是帶有參數 int beginIndex 會回傳以該index為首,直到字串尾的子字串 EX: S1 = "abcdef"; S2 = S1.substring(2); S2 = "cdef" 另一種多載形式帶有兩個參數,int beginIndex 和 int endIndex 按前面的理解就是包含以 beginIndex 為首,endIndex 為尾的子字串 但事實並非如此 S2 = S1.substring(2, 5); S2 = "cde" 這裡的 endIndex 不包含在 substring 也就是範圍 (2, 5) 是2, 3, 4,不包含 5,子字串長度為 3 所以實際上 substring(int beginIndex,  int endIndex)指的是 回傳原字串 從 beginIndex 到 endIndex-1 索引範圍的子字串 為什麼要這樣定義呢? 你可能會發現,此字串的長度可以透過 endIndex - beginIndex 而得 此外,以下式子也成立 substring(a, c) = substring(a, b) + substring(b, c)  (a < b < c) 再者,字串的 index 是從 0 ~ n-1 (假設字串長度為 n ) 因此,我們也可以用這個範圍的子字串代表原字串: 即  s = s.substring(0, n-1) --------------------------------------------------------- 另外一個例子是 Arrays 類別的 fill 方法 可以將一維陣列中特定數量(部分或全部)的元素設定成新的 相同數值 針對不同資料型別的陣列也有不同多載形式 以 int 為例 fill( int[] a, int fromIndex, int toIndex, int val) 參數: a[]  一維陣列 fro...

[Java] UVa 10038 Jolly Jumpers

題目連結 題意: 每組測資先給 n 與該 n 個數字 先求每兩兩相鄰的數字差(絕對值) 判斷這些結果形成的數列是否為 1 ~ n-1 的組合 是則輸出 Jolly, 否則 Not jolly 如: 1 4 2 3 有 4 個 |1-4| = 3 |4-2| = 2 |2-3| = 1 1 ~ 3 恰為 1 ~ n-1 因此為 Jolly 解法: 設一個 布林陣列(可以設上限,以防相減結果超過 n-1範圍) 紀錄兩兩相減的結果到陣列的 index 最後判斷 1 ~ n-1內是否存在沒紀錄的差值即可 程式(Java):

[Java] UVa 488 Triangle Wave

圖片
題目連結 題意: 先告知幾組測資 接著每組測資有兩個數字,Amplitude(Am) 和 Frequency(Fre) 第一個數字與其它測資間都以一行相隔 題目要求輸出 Fre 個三角形 三角形組成是兩端的 1 個 1, 2 個 2,直到中間的 Am 個 Am 如: 2 2 4 6 1 代表兩組三角形 第一組 4 個大小為 2 第二組 1 個大小為 6,如下: 同組的不同三角形與不同組的三角形都以單一空行隔開 解法: 很直觀的題目,多層迴圈即可 不同組之間一個 for loop 同組的不同三角形一個 for loop 每個三角形從邊邊到中間層跑一個 for loop 同一層再一個 for loop 控制輸出幾個數字 程式(Java):

[Java] UVa 10633 Rare Easy Problem

題目連結 題意: 給定一個整數 N (至少兩位數),去掉其個位數後得到整數 M 題目測資給 N - M ,要輸出可能的 N (由小到大排列) 舉例 N - M = 18 若 N = 19,M = 1 若 N = 20,M = 2 解法: 已知 N = 10*M + i ( 0 ≦ i ≦ 9) N - M = 9M + i 則 N =  [(N - M) - i ] / 9  * 10 + i 其中 [(N - M) - i ] / 9 可以得到 M i 只可能為 0, 1, 2, ..., 9 i越大,N值越小,所以從 i = 9開始 依序判斷若 [(N - M) - i ] / 9 為整數,則可得解 (M必為整數) 程式(Java):

[Java] UVa 11716 Digital Fortress

題目連結 題意: 字串長度為平方數時,先按由左到右,由上到下排列(形成n * n方陣) 接著以由上而下,由左而右的方式輸出 例如: 原字串 ABCDEFGHI 方陣的排法: ABC DEF GHI 輸出: ADGBEHCFI 解法: 先判斷字串長度是不是平方數 我取開平方根後的值是否為整數 如 5 的平方根為 2.2..,所以不為平方數 然後用 n * n方陣存字串的所有字元 輸入與輸出的 index 恰好是反向的 像上面的例子中,若B存在 [0][1] 輸出的順序則是[1][0] 將兩個 for loop 的 index 對調輸出即可 程式(Java):

[Java] UVa 11734 Big Number of Teams will Solve This

圖片
題目連結 題意: 每兩行為一組測資,分別代表2字串 進行字串比對,分成三種 Case: 1. Yes: 字串一模一樣 2. Wrong Answer: 字串不一樣,包含大小寫差異或不同字母 3. Output Format Error: 其中一個字串包含空格 解法: 看似很簡單的判定 直覺想到一種情況 如果同時符合 2 跟 3 如何判定? 如: S1 = "A BC" S2 = "ABc" 假設字串的空格消除後仍然不同 似乎要判定成 2 因此,解題思路可以想成先判定 1 與否 若否,就可能為 2 或 3 3 可以看成包含空格的 1 將兩字串的字元一一比對 遇到空格跳過,遇到字元不一樣為 2 若比到尾巴都相符 也就是 3,包含空格的 1 (真正的1一開始就排除了) 上例而言,我們先透過 String 的 equals 方法 (若 S1.equals(S2)回傳為 true,表示S1, S2兩字串相同) 發現不相同,再依序比 1) A 與 A 比 2) 空格與 B 比,S1 右移一位 3) B 與 B 比 4) C 與 c 比,發現不同,判定為 Wrong Answer 程式(Java):

[Java] UVa 11586 Train Tracks

題目連結 題意: 測資一行為一組,包含若干個鐵軌(track) 每個鐵軌都以兩個英文字母表示( M 或 F ) 代表鐵軌的兩端(稱作 connector) 可能是 Male(M) 或 Female(F) 只有 M 對 F 才能將兩個鐵軌相連 題目問每組測資的鐵軌能否彼此相連成一個圓圈循環(cycle) 若是,輸出 LOOP;否則輸出NO LOOP 例如: MF MF MF 第一個的 M 與第二個的 F 相連 第二個的 M 與第三個的 F 相連 第三個的 M 與第一個的 F 相連 可以形成 cycle MM FF 同理,第一個的兩個 M 都可分別與第二個的 F 相連 可以形成 cycle 解法: 首先判斷 若只有一個鐵軌無法形成 cycle 接著,可以發現,不管有幾段鐵軌 要形成cycle的條件就是每個 M 都要跟 F相連 也就是 M 跟 F 的總數要相同即可 ----------------------- 我以每行為單位讀取測資 先確定是否為單一鐵軌(若是,只會有2個字母,字串長度為2) 若否,直接逐一判斷字元 用一個變數,預設為 0 遇到 M 就 ++,遇到 F 就 -- 如果 M F 數量相當 最後變數的值會維持 0 (加上與扣掉相同的值) 藉此判斷最終結果 程式(Java):

[Java] 如何計算對數 log(10)2 或 log(2)4 (以10, 2為底)

圖片
在Java的 java.lang.Math 類別當中 有很多關於數學運算的好用方法 今天要介紹的是高中數學教過的 log (對數) 對數跟指數是相對的概念 2 的 3 次方為 8,2為底數,3為指數 反過來說 log (2) 8 = 3 (以2為底的對數) 當我們想知道8是2的幾次方時就可以使用 常見的是以10為底,所以一般我們說 log 2 就是以10為底的對數 不過在某些數學的世界,反而比較常看到以 e (自然對數)或 2 為底 所以還是要看當下的狀況而定 首先,該類別底下就有 log10 這個方法 所以我們可以直接寫 Math.log10(2) 就會得到double型別的 數值 0.301...( 也就是log 2) 不過,另外只看到 log 方法 他指的是以 e 為底 (如 log(e) 2 = 0.69...) 要如何求以其它數字為底的對數? 還記得高中時學過換底公式,此時就能派上用場 由已知取代未知 我們的已知是以e為底 所以,假設要求 log(2) 4 = log (e) 4/ log (e) 2 即可 程式來說就是 Math.log(4) / Math.log(2) ----------------------------------------- p.s.還記得當初的記法是  log (a) b 的底數 a 比較矮,所以log (c) a擺分母 真數 b 比較高,log (c) b就擺分子 哈哈哈,不然上下記反就錯了

[Java] UVa 10730 Antiarithmetic?

圖片
題目連結 題意: 每行測資給定一個permutation (即 0, 1, . . . , n − 1元素的一種排列),判斷其中是否包含任3個數形成等差數列,若否,稱為 antiarithmetic permutation,輸出yes;若存在,輸出no 例如: 4 5 0 3 1 2 其中的 4 3 2 是等差數列,所以要輸出 no 解法: 一開始我用暴力解,每次找到等差前、中項後 都會一一走訪到數列尾以找後項,果不其然TLE了 包含透過Arraylist 的 indexOf 方法 時間複雜度可能落在 O(N^3)... (Worst case 前中後項) 後來只好爬文 看到網路上大多是在讀取數列的同時記錄位置 因為permutation就是該數列恰包含 0 ~ n-1 的元素 我們只要倒過來 用陣列的 index  表示真正的數值 陣列存的 值 則為原本數列的位置所在 以 4 5 0 3 1 2 為例 陣列第 4 格擺 0, 第 5 格擺 1, 第 0 格擺 2, 依此類推 從陣列裡,我們可以知道 數值 0 在原數列 2 的位置 數值 1 在原數列 4 的位置 ... 而3元素的等差數列的定義為:  前項, 前項+公差, 前項+2*公差 也就是我們只要依次判斷 arr[0], arr[1], arr[2] (公差1) arr[0], arr[2], arr[4] (公差2) arr[1], arr[2], arr[3] (公差1) arr[1], arr[3], arr[5] (公差2) ... 存的值是不是遞增(也就是在原本數列也是照順序出現) 或是遞減(公差為負的情況) 像這個例子,arr[0], arr[1], arr[2]遞增,所以輸出 no 大概評估一下,時間複雜度應該在O(N^2)以下 (前項N,公差從1枚舉到 後項到數列長度前) 程式(Java):

[Java] UVa 10025 The ? 1 ? 2 ? ... ? n = k problem

圖片
題目連結 題意: 給定一個式子 ? 1 ? 2 ? ... ? n = k , 其中 ? 可以為 + 或 - 題目給 k 值,要求輸出最小的 n 使得式子成立 舉例: k = 0, 存在最小的 n = 3 使得 1+2-3 = 0 k =12,存在 n = 7 使得 -1+2+3+4+5+6-7 = 12 解法: 觀察式子,可以知道式子是從 1 ~ n 的運算 例如: 假設 n 為 3,式子的最大發生在運算子都是 + (最小則為 - ) 即 +1+2+3 = 6 (最小為 -1-2-3 = -6) 再觀察發現,改變任何運算子後的結果都跟原來的差為偶數 綜觀來看,n = 3時會有以下運算結果 +1+2+3= 6 -1+2+3= 4 +1-2+3= 2 -1-2+3= 0 -1+2-3= -2 +1-2-3= -4 -1-2-3= -6 因此,我們可以先求得最大值,判斷 k跟它是不是差偶數倍 以上面的例子,假設 k 為 0 ,可以得到(6 - 0) %2 = 0 意思是可以從 +1+2+3的式子透過改變運算元得到 k 的結果,則答案 n 可以為 3 因為題目要求符合答案最小的 n 解題思路為 如果存在 1+2+3+...+n = k,該 n 必為最小 否則 k 就是 將式子結果 扣掉偶數 得到 因此 題目給定 k,透過上圖公式得到最小候選 n (真正的 n 會大於等於該數) 並計算該 n 下的式子結果最大值(即 1+2+...+n) 再判斷該值與 k 值的差是否為偶數(前提是比k大,才能改運算元去得到k) 若否,增加 n 的值並重複判斷 舉例來說 k =12,最後答案 n = 7 先以上圖公式得到n = 4 (4.xxx取整數) 4*5/2 = 10,比 k=12 小 n = 5,5*6/2 = 15,15與k=12的差不為偶數 n = 6,6*7/2 = 21,理由同上 n = 7,7*8/2 = 28,符合結果,答案為 7 程式(Java):

[Java] UVa 10703 Free spots

圖片
題目連結 題意: 大意是給定一個長方形的長與寬 還有若干個小長方形(座標) 求原長方形內未包含在小長方形的面積大小 每組測資由3個數字為一行開頭 分別為W, H, N,W, H代表長方形的寬, 高 N為 後面還有 N 行測資,代表 N 個小長方形 每行分別有4個數字,為小長方形的對角線座標 舉例而言,有一組測資為: 4 3 1 1 2 4 3 表示有個4 * 3長方形 與一個對角座標為(1, 2), (4, 3)的小長方形(下圖紅框處為對角座標) 則剩餘面積為 4 解法: 根據大長方形的寬, 高建陣列 走訪每個小長方形佔到的面積做註記(如圖上綠色部分) 最後統計陣列內還沒註記的總和即可 要注意小長方形測資並沒有保證前者的座標會小於後者 也就是不一定為左下-右上的座標對 如上圖,也可能是(1, 3), (4, 2)(指的是相同小長方形) 不過,不論是何者,我們的目標是該綠色部分都要註記即可 迴圈部分可以這樣寫: for (int i = Math.min(a1, b1); i <= Math.max(a1, b1); i++) for (int j = Math.min(a2, b2); j <= Math.max(a2, b2); j++) (a1, a2) (b1, b2)分別為2個對角座標測資 程式(Java):

[Java] UVa 12439 February 29

圖片
題目連結 題意: 一般而言,我們知道每 4 年會出現一次 2月有 29 天 多出來的 2/29 叫做 leap day (閏日) 題目先告知閏日的規則: 西元年為4的倍數會閏;100的倍數不閏;400的倍數卻又閏 即,西元 4, 8, ... 會閏 但遇到西元100, 200, 300, 500, ... 不閏(400倍數可閏) 其實這樣的規則還少了4000的倍數又不閏,但此題依照題意描述為準 相關規定可以參考  這則新聞 測資方面,先告知會有幾組,每組有兩行分別代表一段區間頭尾 要計算這段區間內的閏日數(即 2/29出現次數) 解法: 計算一段區間內的值,最快的做法就是計算頭尾兩者之差 如上圖,以西元0年為基準 假設測資頭尾是 a 與 b 先個別統計從0年到a b的閏日數(leap a, leap b) 兩者相減即為所求 根據規則,要計算leap數 拿該西元年/4後,扣掉/100的值,再加上/400就是了 還要探討兩個條件: 1. 若 a 或 b 的年份恰好為閏年 上述的 leap 計算是包含該年 如果日期是1/1~2/28,該年的閏日是不能加進去的 例如: 西元4年 1/2,如果不判斷,leap數是1 事實上從0年到此區間leap是 0 (把西元4年算進去了) 2. 計算頭的時候,如果日期恰好為2/29,也要先扣掉 否則頭尾都會計算到,相減時就抵銷了 例如: 西元4年 2/29 ~ 西元4年 3/2,如果不先扣,leap數分別都是1 相減為0,但這個區間是有一個leap的(即2/29) 程式(Java):

[Java] 基本資料型別 - int 和 long

這篇是針對UVa來寫的 我們做題目的過程,不外乎先要檢查輸入測資的範圍 大部分的題目是要進行數學運算的 但如果使用的變數型別與測資範圍不同,勢必會出錯 例如: 測資會給到 100位數 的十進位數字 不管用int, long等都會超過 所以只能使用字串來做 或透過 BigInteger 類別(專門處理大數運算) 因此,這邊介紹基本型別的範圍(主要是 int 與 long ) 希望面對題目時,能真對測資使用適合的變數型別來答題 ----- 在Java當中,不同的資料型別所佔用的記憶體不盡相同 我是透過記憶這些大小來對應到他們的範圍 像 int ,占用4 bytes (32bits) 理論上 1 bit 可以存 0 或 1  (2個數) 2 bits 可以存 4個數 ... 32 bits 就可以存到 2^32 個數 不過,變數的第一個 bit 存的是 sign ,也就是正負號 (0為正, 1為負) 像 2 bits 對應為 00(0) 正數 01(1) 負數 10(-2), 11(-1) 3 bits 對應為 000(0) 正數 001(1), 010(2), 011(3) 負數 100 (-4), 101(-3), 110(-2), 111(-1) 不看sign bit,負數的存值方式跟正數稍有不同 因此 int 的範圍為  -2^31 ~ 2^31 - 1 (包含 0,總共也是 2^32個數) 同理,long 的 大小為 8 bytes (64 bits) 能存的範圍就是 -2^63 ~ 2^63 - 1 此外,int 的範圍 -2^31  = -2147483648 (約負的10的9次方) 2^31 - 1  = 2147483647 (約10的9次方) long則為  -2^63   = -9223372036854775808 (約負的10的18次方) 2^63 - 1   = 9223372036854775807 (約負的10的18次方) long 在 10 進位與 2 進位的範圍,其次方大概都是 int 的 2 倍 可以大概記住 ...

[Java] UVa 11764 Jumping Mario

題目連結 題意: 每組測資有若干高度的牆,Mario站在第一個 計算從第一個到最後的過程,高度增加與減少的次數 例如: 高度 1 ~ 2 增加 高度 3 ~ 2 減少 高度 2 ~ 2 不計算 解法: 開一個陣列,用一個變數存當前的高度,依序判斷即可 程式(Java):

[Java] UVa 11827 Maximum GCD

題目連結 題意: 一序列兩兩計算最大公因數(GCD),求出最大值 解法: 主要是 GCD 的計算,在自定義的 getGCD 方法中 用遞迴的手法實現類似輾轉相除法求 GCD 參數 a, b 若 a > b,a % b就是 a 一直扣掉 b直到剩下小於b的數 當這個數為0,則輸出 b (表示當下的 b是 a 的因數,更是 a b的GCD) 若 a < b, a % b = a getGCD(b, a%b); 等於把兩數交換放參數再做一次 也因此此方法可適用所有情況(不論a b誰較大) 依序倆倆呼叫 getGCD 方法,最後輸出最大值即可 程式(Java):

[Java] UVa 10115 Automatic Editing

題目連結 題意: 每組測資會先告知有若干組替換詞 每兩行分別代表 替換前 與 替換後 ,為一組替換詞 最後是一行原始字串 看似很像word等文書編輯軟體會有的取代功能,但詳讀文章後,會發現有順序性 做法是從第一組替換詞開始搜尋,若有目標(替換前)存在,每次取代  一次 意思是要一步一步來,而不是一次全部換 例如有一組替換詞, AB 換 BA 原本長這樣:ABABAB 一次一次取代: AB ABAB -> BA AB AB -> B AB AAB -> BBAA AB -> BBAABA 一次全部取代: ABABAB -> B ABAB A -> BB AB AA -> BBBAAA (紅色表示當下要被替換的目標) 所以要用String類別的 replaceFirst 方法,而不能用到 replaceAll 方法 最後結果可能有所不同 解法: 程式(Java):

[Java] UVa 10978 Let’s Play Magic!

題目連結 題意: 環狀排列的牌,玩法是每次根據"指令的字母數"移動若干步 走到一張目標牌並移除,一直到最後 這題給你所有指令與拿走的牌,要問原始的牌順序為何 輸入測資先給定 N 張牌 接著 N 行依序是牌的名稱與指令 (第 N 個指令拿走最後一張牌) 輸出則為原本的牌(按順序列出名稱) 如範例測資: 原始有13張牌 QH 4C AS 8D KH 2S 7D 5C TH JH 3S 6C 9D 第一個指令是ACE(3步),會拿走AS,也就是第3個位置是AS 拿走AS後長這樣 : QH 4C 8D KH 2S 7D 5C TH JH 3S 6C 9D 第二個指令是TWO(3步),繼續走3步,會拿走2S,也就是"原本的"第6個位置是2S 拿走後長這樣 : QH 4C 8D KH 7D 5C TH JH 3S 6C 9D 第三個指令THREE(5步),拿走3S後: QH 4C 8D KH 7D 5C TH JH 6C 9D 第四個指令FOUR(4步),從6C開始,到9D後會從頭QH開始,拿走4C QH 8D KH 7D 5C TH JH 6C 9D 依此類推... 解法: 要根據指令重建序列 已知的是會從頭開始 根據指令重建即可 配合一個布林陣列,如果已經移除的改成true 下次走訪就直接略過 例如要走3步,第3步遇到已經移除的 就依序往下找 程式(Java):

[Java] UVa 10252 Common Permutation

題目連結 題意: 此題輸出入都是小寫字母 每兩行為一組測資,分別代表兩序列 (A 和 B) 輸出共同存在 A 和 B的字母 如果某字母出現不只一次,就要印出 A 和 B 之間較少的次數 如: A = abccc , B = accd,則輸出 acc 以字母 a ~ z 的順序印出 解法: 以兩陣列分別統計兩序列所有元素出現次數 輸出時,從 a 開始,依序印出兩陣列次數大於0且較小次數的字母 其中,小寫 a~z 的 ASCII 為從 97~122 程式(Java):

[Java] UVa 10282 Babelfish

題目連結 題意: 字典翻譯對照,測資前半每行以空格區別語言 A 與 B, 後半每行為語言B的文字,要輸出對應的語言 A 文字 A 與 B的文字都由一個單字組成(不含空白的英文字母序列) 若找不到對應的 A ,輸出 eh 解法: 透過 HashMap,Key - Value配對 put(Key, Value) 方法放資料 get(Key) 方法以參數 Key 取得回傳值 Value containsKey(Key) 方法判斷是否存在該 Key - Value 因為題目要以 B 搜尋 A,HashMap 的 get 參數為 Key 所以我把 A 當作 Value,B當作 Key 實作 程式(Java):

[Java] UVa 11743 Credit Check

題目連結 題意: 每組測資含16位數字(4個4位) 將奇位數字分別*2後,各位數相加得到一個數 sum1 偶位數字相加得到一個數sum2 將sum1 + sum2相加後,若尾數為 0 輸出 Valid,不為 0 輸出 Invalid 解法: 單純的照著做即可,我把每一組測資當成4個4位數字來讀 分別進行各位數的動作,最後判斷一下 %10 的結果 其中奇位數*2後要判斷是否變成2位數字,如6*2=12,就要sum1 += (1+2) 程式(Java):

[Java] UVa 10611 The Playboy Chimp

題目連結 題意: 猴子?(之類的生物...)的選美大會 測資只有一組,前半先提供有 N 隻母猴的身高(已遞增排序) 然後有Q個query,可以看成要解Q組答案 每組提供一個公猴身高值,要從母猴當中求: 1. 小於公猴身高的最大值 2. 大於公猴身高的最小值 解法: 看完範例輸出入就很好下手 先用陣列存所有母猴身高,連排序都省了 首先判斷第1個輸出 先從陣列尾端往回搜尋,第一個比公猴小的就是答案 搜到陣列頭還沒結果就輸出X 第2個輸出同理 從頭到尾第一個比公猴大的就是答案 程式(Java):

[Java] UVa 11364 Optimal Parking

題目連結 題意: 一條數線(很長的道路)上,每組測資會有若干個點(商店), 選定任意位置停車,要輸出走訪各點並回到停車處的最小距離。 解法: 不管在哪停車,走訪各點並回到停車處最近的方式是, 分別往返停車處的左與右邊最遠的點(途中會經過其他點,也算走訪)。 因此,題目可以看成計算兩個相隔最遠的商店距離 也就是求這些點當中,座標最大與最小之差的兩倍(來回) 程式(Java):

[Java] UVa 11388 GCD LCM

圖片
題目連結 題意: GCD(G) 表示最大公因數,LCM(L)表示最小公倍數。 每組測資給定 G 和 L,求兩數 a, b 其最大公因數與最小公倍數恰為G與L,且 a 為最小,若不存在則輸出 -1 解法: 因此,題目要求兩數之最大公因數等於前者,最小公倍數等於後者 也就是若後者為前者的因數,就輸出 G 與 L,若否則輸出 -1 程式(Java):

[Java] UVa 11115 Uncle Jack

題目連結 題意: 叔叔有若干片CD要分給若干個姪子女,求分法(可能有人沒分到) 解法: 有幾個姪子女,每片CD就有幾種分法,(如有一片,要分給3個人,有三種可能) 假設N個人,要分D片CD,就有N^D種(次方),很直觀的解法 原本我用int long,會爆掉 (當N=10, D=25,結果為10000000000000000000000000,即10^25) 最後偷懶使用 BigInteger,輕鬆解決 程式(Java):

[Java] UVa 10954 Add All

題目連結 題意: 每組測資給若干數字求總和,每次任兩數相加,直到最後。 過程中產生的和會形成cost 例如: 1+2=3 (cost 3) 若有 1, 2, 3 三數 選擇 1+2,再+3,則是 1+2 = 3 (cost 3) 3+3 = 6 (cost 6) 總cost為 9 也可以先2+3再+1 2+3 = 5 (cost 5) 5+1 = 6 (cost 6) 總cost為 11 題目要求輸出最小的 cost 解法: 上例中,最早進行計算的會產生最多次 cost 因此,要從最小的數開始 每次加完後也會成為下次可能相加的元素 做法是每次抓出最小的兩數相加 計算 cost 並將結果放回去,可以得到最小的總 cost 我們選用 PriorityQueue 資料結構,放進去的數字會自行 sort(由小到大) 放進去是 add 方法,取出是 poll 方法,每次 poll 會得到最小的值 程式(Java):

[Java] UVa 10055 Hashmat the brave warrior

題目連結 題意: 一個將領在戰場上,要求自己跟敵方的士兵數量差距。 測資是彼此的士兵數。 解法: 求兩數之差即可,但數字可能到2的32次方,所以資料結構要用long。 可以用絕對值求解,或是先判斷誰大,再扣掉對方。 程式(Java):

[Java] UVa 10035 Primary Arithmetic

題目連結 題意: 每組測資包含兩個數字(位數不一定相同),計算加法過程進位的次數 解法: 必須從個位開始,因為前一位的進位可能影響下一位數。 因此,如果有進位,計算下一位時要特別加上。 另外,位數不同也要能計算,如: 99跟1,個位發生進位。 十位只有9,加上個位進位,所以也有進位,答案是2次。 程式(Java):

[Java] UVa 11044 Searching for Nessy

圖片
題目連結 題意: 看來是跟尼斯湖水怪有關的題材,重點從第三段開始,Given a grid of... 測資提供一個n * m的網格,要在網格內放類似監視器的東西(大概吧) 每個監視器可以涵蓋一個九宮格的範圍 求最少需要多少監視器(不含最外圈,即示意圖藍色部分) 解法: 看起來是很麻煩的空間題目,右邊只是故意放得很複雜 為了符合最低需求,只要設想藍色範圍需要多少監視器即可 對於網格 m 或 n 而言,每個監視器都佔相同3格範圍 所以可以m n分別以3為單位區分來算 假設邊長6 (m n皆 ≧ 6),監視器要涵蓋 4,最少需要2台(3*2 = 6需 ≧ 4) 邊長7時涵蓋5,需要2台 邊長8時涵蓋6,需要2台 邊長9時涵蓋7,需要3台 ... 可以發現所需監視器數恰等於邊長除以3 結果為column * row 程式(Java):

[Java] UVa 10215 The Largest/Smallest Box ...

圖片
題目連結 題意: 數學題,一個長方形,4個角落各消掉邊長為x的正方形,測資給定長方形的長L與寬W,求x的值使體積能最大與最小 解法: 如上圖,可以得知體積為V = (L-2x) (W-2x)x,微分後使式子為 0 可以得到原體積最大 以二元一次方程式公式就可求出x 而要使體積最小(V = 0),可令x = 0,或x = min(W/2, L/2)(使長邊或短邊最短) 程式(Java):

[Java] UVa 11063 B2-Sequence

題目連結 題意: 給定一組遞增序列,將其任兩數相加之和不可重複(包含自己與自己相加) 如1, 2, 4, 8 任兩數相加有: 1+1, 1+2, 1+4, 1+8, 2+2, 2+4, 2+8, 4+4, 4+8, 8+8 其中測資元素大小不超過10000 解法: 當下看到第一個直覺是用一個陣列存總和列表,要放新的前先檢查有無重複 但因為是任兩數相加都要比,數字一多搜尋重複所耗費時間也很可觀 後來發現可以改良陣列,用陣列index當作總和 因為數字上限10000,任兩數之和不會超過20000 設立布林陣列,預設false,相加判斷index 為true表示已出現過,就不是B2-Sequence 切記換下一組測資前要重設陣列 程式(Java):

[Java] UVa 10062 Tell me the frequencies!

題目連結 題意: 很好理解,測資以換行做區隔 讀取每個字元統計出現次數,頻率由小到大印出 每個字元結果分別印對應ASCII號碼與次數,次數相同則先印大者 解法: 我用二維陣列來統計,[0]是ACSII,[1]是次數 排序稍微複雜,我透過Arrays.sort方法,搭配自訂Comparator(比較的根據) 先比較次數, if  (x[1] > y[1])   return 1,也就是前者(大的)先排(由大到小) 同理,if (x[1] < y[1])   return -1,也就是後者(大的)先排(由大到小) 次數相同再比ASCII,也同理 另外要注意每筆測資的結果之間要多空一行,即第二筆資料後先空行再輸出結果 每次統計完,進行新測資前也要清空陣列 程式(Java):

[Java] UVa 10018 Reverse and Add

圖片
題目連結 題意: 測資每次輸入一個數字,將數字加上其反轉的值後,觀察結果是不是palindrome(從左而右或右到左是否相同,亦即原數是否等於其反轉的數),若否,重複前面動作直到求出palindrome,最後印出進行次數(相加)與最終結果 解法: 先寫出反轉的方法,遞迴進行,每次判斷反轉前後是否相等,若否則相加繼續判斷,題目有先決條件: 1.必定有解 2.遞迴次數小於1000(其實我一開始擔心TLE,因為反轉的寫法可能不精簡,但卻發生另一件事..) 3. 結果不超過4,294,967,295(超過int的上限,本來出現WA還想不出理由,最後改成long解決) 程式(Java):