# 題目: UVa 11489 - Integer Game # 題目說明 有兩位玩家S與T要玩一個回合制遊戲，由S先行動 從N開始，每位玩家要輪流移除一個字元的數字 條件為: 移除後所有數字相加需要為3的倍數 當剩餘一個數字時，可以直接移除 誰先不能移除數字誰就輸了 例如當N = 1234 可以移除4，會使得剩下的數字1 + 2 + 3 = 6為3的倍數 也可以移除1，會使得剩下的數字2 + 3 + 4 = 9也為3的倍數 INPUT: 第一行輸入一個整數T，代表測資數 每筆測資輸入一個整數N OUTPUT: 輸出S(S贏)或T(T贏) # 解題方法

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

# 題目: 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 <iostream&g

# 題目: 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，設一個變數

# 題目: 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 = (總人數 * 每人最多支付金額) / 服務費 - (每個人的茶費) 寫成數學算式如下: P = (++N * x) &#

# 題目: 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的餘數 若為負數，num2[i] = num[i

# 題目: 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] += dp[i - prim

# 題目: 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 subsequence INPUT: 第一行有一個整數S，代表測資數 每筆

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