# 題目: UVa 10921 - Find the Telephone # 題目說明 你需要將一串訊息轉換成對應的號碼 INPUT: 每筆測資輸入一個字串 str OUTPUT: 輸出轉換後的字串 # 解題方法 純粹的條件判斷後輸出即可 # 參考程式碼 #include <iostream>using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string str; while (cin >>...

# 題目: UVa 12019 - Doom's Day Algorithm # 題目說明 給一個日期 M 月 D 日 求 2011年M月D日 是星期幾 已知: 4/4 、 6/6 、 8/8 、 10/10 、 12/12 都是星期一 INPUT: 第一行輸入一個整數 N ，代表測資數 每筆測資輸入兩個整數 M 、 D ，代表 M 月 D 日 OUTPUT: 輸出 2011年M月D日 是星期幾 # 解題方法 先建一個每月有幾天的陣列 將 2011年1月0日 到 2011年M月D日 的總天數算出來 %= 7 後輸出即可 # 參考程式碼 #include...

# 題目: UVa 725 - Division # 題目說明 輸入一個範圍 2 ~ 79 的整數 N ，找到 abcde / fghij = N abcdefghij 為 0 ~ 9 不重複數字 INPUT: 每筆測資輸入一個整數 N 當 N 為 0 時結束 OUTPUT: 輸出所有符合條件的 abcde / fghij = N ，以升冪排序 如果都不符合條件，輸出 There are no solutions for N # 解題方法 採取暴力破解法 先將條件置換成 abcde / N = fghij abcde 的範圍為 01234 ~ 98765 ，設一個變數 i 除以 N 若 i...

# 題目: UVa 11566 - Let's Yum Cha # 題目說明 中文題目說明 INPUT: 第一行輸入 4 個整數 N 、 x 、 T 、 K 你與 N 位朋友去飲茶，每人最多付 x 元，需要支付 T 元的茶費，總共有 K 種點心可以點 接下來有 K 行，每行有 N + 2 個整數，第一個為點心的價格，後面 N + 1 個為每人的滿意度 當 N 、 x 、 T 、 K 為 0 時結束程式 OUTPUT: 輸出最大的 mean favour value # 解題方法 先計算預算 P P = (總人數 * 每人最多支付金額) / 服務費 -...

# 題目: UVa 10616 - Divisible Group Sums # 題目說明 給一個有 N 個數字的序列，取出 M 個數字相加，使結果能整除 D ，求總方法數 INPUT: 每筆測資第一行輸入兩個整數 N 、 Q 接下來有 N 行，每行輸入一個整數 接下來有 Q 行，每行輸入兩個整數 D 、 M 當 N 、 Q 為 0 時結束程式 OUTPUT: 輸出符合題目條件的總方法數 # 解題方法 此題為 knapsack problems (背包問題) 需要先將輸入的 N 個數字 ( num[i] ) 做處理 若為正數， num2[i] = num[i] % D ，直接取 D...

# 題目: UVa 1213 - Sum of Different Primes # 題目說明 求將 K 個小於等於 N 的質數相加後等於 N 的方法數量 例如: N = 24 、 K = 3 則答案有 2 種 INPUT: 每筆測資輸入兩個整數 N 、 K 當 N 與 K 為 0 時結束程式 OUTPUT: 輸出 dp[N][K] # 解題方法 此題為 knapsack problems (背包問題) 先將 <=1120 的所有質數找出，存入 prime 定義一個 dp[i][j] i 為當前的 N ，也就是能取到的最大數字 j 為相加的質數數量 dp[i][j]...

# 題目: UVa 11790 - Murcia's Skyline # 題目說明 有 N 棟建築，每棟建築有 高度h 與 寬度n 你需要依照高度找出從左至右的 longest increasing subsequence 與 longest decreasing subsequence 將這些 subsequence 的 w 加總，各找出某一個序列的最大 w 合，稱為 w(in) 與 w(de) 若 w(in) 比 w(de) 大，則先輸出 longest increasing subsequence 反之則先輸出 longest decreasing...

# 題目: UVa 481 - What Goes Up # 題目說明 給一串整數序列，找出 最長的嚴格遞增子序列 ( strictly increasing subsequence ) INPUT: 輸入一連串的整數 OUTPUT: 輸出 最長的嚴格遞增子序列 的長度與其中的元素 (若有多組元素的長度一樣，以最後出現的為準) # 解題方法 將資料存取後，利用貪婪演算法找出嚴格遞增子序列的長度 紀錄每次選取的位置 vector V 儲存輸入的整數 vector S 儲存現在的嚴格遞增子序列 vector dp 儲存元素的位置 若使用動態規劃，時間複雜度會為 O(N^2)...

# 題目: UVa 11456 - Trainsorting # 題目說明 一節車廂可以選擇放在火車頭或火車尾 車廂必須按照重量由重到輕從火車頭開始排列 你需要找到最多能連接幾節車廂 INPUT: 第一行有一個整數 S ，代表測資數 每筆測資第一行有一個整數 N ，代表車廂數 接下來 N 行，每行有一個整數，代表車廂的重量 OUTPUT: 輸出最多能連接幾節車廂 # 解題方法 這是 Longest Increasing Subsequence ( 最長遞增子序列 ) 的問題 由於車廂可以排在前後，所以我們將輸入的資料複製一份顛倒放在前面 例如: N = 3 1 2 3 則排成: 3 2...

# 題目: UVa 11420 - Chest of Drawers # 題目說明 題目中的櫃子由數個抽屜堆疊而成，但是這種櫃子有安全上的疑慮 若你將一個抽屜完全抽出，那你能拿到下一層抽屜的東西 當前有 L 個抽屜，有 S 格是完全安全的，求總共有幾種排列法？ 例如: L = 6, S = 4 則有 6 種可能 U L L L L L L U L L L L L L U L L L L L L U L L L L L L U L L L L L U U ( L 為上鎖的， U 為未上鎖的，粗體為不安全) INPUT: 每筆測資輸入兩個整數 L 、 S...