題目： UVa - 389 - Basically Speaking 題目說明給一個字串表示數值，及 n、m，表示該值是 n 進位，要求轉換為 m 進位。 除此之外，有三個要求: 轉換後不可超過 7 位數，若超過則輸出 "ERROR"。 字串只會出現 A ~ F 及 0 ~ 9。 n、m 的範圍為 2 ~ 16。 且輸出時需靠右對齊。 Input： 每行有三個變數，分別為該字串、n、m Output： 輸出轉換後的數值。 解題思路根據題目要求做轉換，先轉換為十進位再轉換成題目要求的進位數，需要注意的是要靠右對齊，所以不足 7 位的要補上空白。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::s ...

題目： UVa - 458 - The Decoder 題目說明給一個加密後的字串，找出加密的規則並且輸出解密後的字串。 Input： 每行都是一個加密的字串。 Output： 輸出解密後的字串。 解題思路先觀察 Sample I/O，找一些相同的字比對，可以發現加密方法應該是加上某個偏移量而成。找任意一組字串相減可以知道偏移量為 7，最後對每個字元做偏移即可得到解密後的字串。 參考解法123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();int main(){ string str; while (getline(cin, str)) { for (auto& ch : str) ch -= ...

題目： UVa - 10050 - Hartals 題目說明給某個天數及一些團體罷工的週期，從週日開始，週五及週六不算，求在這些天數中，罷工的天數為多少 ( 只要任意團體在該天罷工則該天視為罷工 )。 Input： 第一個整數 T，表示有 T 組測資，後面兩個整數 N、P，分別代表天數及團體的數量，後面 P 個整數表示各團體罷工的週期。 Output： 輸出罷工的天數。 解題思路先讀取測資，之後根據題意模擬即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>using namespace std;// reference: https://ppt.cc/fgtWRxstatic auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();in ...

題目： UVa - 11633 - Food portion sizes 題目說明學生餐廳為了不讓學生餓肚子，以及方便他們為每一個學生製作餐點，每一份餐點的量都會相同，然而一份餐點對於某些學生來說太少，因此必須多跑幾次餐廳才能吃飽，已知每位學生不會跑大於 3 次餐廳，而每位學生只會吃自己所需要的份量，剩餘的份量就是浪費。 請最小化 ax + by，其中 a, b 為給定的常數，x 為所有學生所製造的廚餘，y 為所有學生跑餐廳次數的總和。 引用自：UVa 11633 - Food portion sizes | Morris Blog Input： 每組測資第一個數字 N，表示有幾位學生，後面兩個整數分別代表 a、b，之後 N 個整數表示每位學生的食量。 Output： 輸出 ax + by 的最小值，若不為整數，請輸出為約分後的分數型態。 解題思路由於輸出格式的原因，所以要避免再計算的時候出現小數，因此先將所有學生的食量都乘以 6，因為每位學生可能會去餐廳 1 ~ 3 次，這樣每份餐點的量就會是整數。 之後暴力法模擬每位學生去餐廳 1 ~ 3 次的情況下每份餐點的量，計算出 ax ...

題目： UVa - 12319 - Edgetown’s Traffic Jams 題目說明給一個無向圖及一個有向圖，兩圖上的點數量一樣，求任兩點的最短路徑在有向圖上是否大於在無向圖上的 A 倍加 B。 Input： 每組測資第一個整數 N 表示有 N 個點 **( 編號為 1 ~ N )**，後面 N 行依序為無向圖的連接情況，再後面 N 行依序為有向圖的連接情況，每行至少有一個整數 u，後面的數字表示有 u 到該數字的邊，且邊的路徑長為 1。 Output： 若任兩點的最短路徑在有向圖上大於在無向圖上的 A 倍加 B 輸出 “Yes”，否則輸出 “No”。 解題思路這個解法需要有 Floyd-Warshall 演算法的概念。 先讀取測資，若任兩點沒有邊連接，則路徑長初始化為無限大( 1e9 )，之後使用 Floyd-Warshall 演算法找出圖上任兩點的最短路徑，再依照題目要求判斷即可。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 ...

題目： UVa - 11960 - Divisor Game 題目說明給一個整數 N，求小於等於 N 的正整數中，因數最多的數字，若有相同則取較大者。 Input： 第一個整數 T，表示有 T 組測資，後面 T 行每行都有一個整數，代表 N。 Output： 輸出小於等於 N 的正整數中，因數最多的數字，若有相同則取較大者。 解題思路解法一: 想知道每個數字的因數個數，可以使用一個數組保存並初始化為 1，因為每個數都至少有一個因數，接著遍歷陣列，將所有數字的倍數都加一，最後就可以得到所有數的因數個數，最後根據題目的要求更新數組並輸出答案即可。 解法二: 一個正整數的所有因數其實都是該數質因數的組合 ( 可參考本篇文章: 演算法課程題解 - 基礎數論 3 - HackMD )，因此要知道該數因數的個數，需要先做質因數分解，可以先使用質數篩 ( 可參考本篇文章: 演算法筆記 - Prime )，找出每個數的最小質因數，接著遍歷陣列，將數字不斷除以自己的最小質因數即可完成質因數分解。接著根據題目的要求更新數組並輸出答案即可。 參考解法解法一123456789101112131415161 ...

題目： UVa - 11536 - Smallest Sub-Array 題目說明給三個整數 N、M、K，依據題目的要求建出一個陣列，從這個陣列中找出包含 1 ~ K 的最小子陣列的長度。 Input： 第一行為一整數 T，表示有 T 組測資，後面 T 行每行有三個整數，依序為 N、M、K。 Output： 輸出最小子陣列的長度。 解題思路先依照題目要求算出陣列，之後遍歷陣列，紀錄符合條件的數字最後出現的位置同時將符合條件的數字的位置推入 Queue 中，同時檢查，若 Queue 中最前面的數字在後面出現過就移除，原因在於，目前取到的子陣列其實是 **Queue.front() ~ i**，若 Queue 中最前面的數字在後面出現過就相當於前面一部份的元素是多餘的，可以捨去，使得子陣列縮小。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <bits/stdc++ ...

題目： UVa - 10415 - Eb Alto Saxophone Player 題目說明給薩克斯風的各種音調的指法，及由這些音調組成的歌曲 ( 假設一個手指頭只能按特定一個按鍵，且不同手指控制不同按鈕 )，求每根手指需要按下的次數，如果某一按鍵在下一音符時不會用到，那麼就會放開，否則就是維持按著的情況。 Input： 第一個整數 T，表示有 T 組測資，後面 T 行每行為一首歌曲，歌曲可能為空。 Output： 對於每組測資，請輸出 10 個數字，代表每個手指的按下次數，數字用空格分隔。 參考自：e531. 10415 - Eb Alto Saxophone Player - 高中生程式解題系統 解題思路先建表，建立音調及手指的映射，之後查表即可，需要注意的是由於歌曲可能為空，所以使用 getline() 讀取，還需要紀錄上一個音調按下的手指，並在計算次數時比對。 參考解法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 ...

題目： UVa - 10188 - Automated Judge Script 題目說明給兩組字串，根據條件分成三種結果。 Accepted: 兩組字串完全相同 ( 包括換行及空白 )。 Presentation Error: 兩組字串數字部分的順序相同。 Wrong Answer: 以上兩者皆不符合。 Input： 每組測資第一行為一整數 n，代表第一組字串有 n 行，後面 n 行為第一組的字串，再下一行為一整數 m，代表第二組字串有 m 行，後面 m 行為第一組的字串 Output： 根據條件輸出結果。 解題思路使用 String 來保存兩組字串，並在讀取的時候加入換行符 '\n'，之後先比對是否 AC，若不是則取出數字的部分比對是否 PE。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;static au ...

題目： UVa - 11689 - Soda Surpler 題目說明有一個人很喜歡喝汽水，汽水可以使用空瓶兌換，每組測資給三個整數 e、f、c，分別代表 初始擁有的空瓶數量、找到的空瓶數量、兌換一瓶汽水需要的空瓶數量。 Input： 第一個整數 T 代表有 T 組測資，每組一行，每行有三個整數分別代表 e、f、c。 Output： 輸出最多能喝到幾瓶汽水。 解題思路根據題意模擬即可，e + f 為一開始擁有的空瓶數量，需要注意的是，兌換到的汽水也要加進空瓶的數量。 參考解法12345678910111213141516171819202122232425262728293031#include <iostream>using namespace std;static auto __ = []{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();int main(){ // e -> empty, f -> fou ...