技藝編程

  題目敘述 本題採EOF方式收資料，每筆資料有兩個1~1000000的正整數A和B。要求輸出A和B還有「 從A到B的3n+1 Problem的總Cycle次數最多的次數」。 3n+1: 如果N=1，return 1。 如果N是偶數，return N/2。 如果N是奇數，return 3N+1。 範例輸入 #1 1 10 100 200 201 210 900 1000 範例輸出 #1 1 10 20 100 200 125 201 210 89 900 1000 174 解題思路 本題可以用建立1到1000000的表來做，但是要跑1000000次的3N+1函式還是很耗時，可以發現當N可以被2整除時，他的3N+1函式回傳值就會是N/2的回傳值再加1，利用這點只需要判斷1到1000000中的奇數就好了。但是這樣子還是不夠快，所以除了將3N+1函式的回傳值進行建表，還需要進行A到B的最大值的線段數建立，最後再建立一個Query的函式將A到B的最大值進行計算，這樣子就不會TLE了。另外，測資中有可能A會大於B，這種情況就需要Swap(A, B)，但是輸出的時候還是要按照原有的順序進行輸出，這點需注意。

題目敘述 每筆測資第一行有六個正整數N、M、R1、C1、R2、C2，接下來要輸入一個N乘以M的二維字元。R1到R2代表上下，C1到C2代表左右，要求輸出這個二維字元中的R1~R2、C1~C2的字串。 範例輸入 #1 10 14 4 3 10 9 VBREEFISHRACHP ANACROCODILEEB AOSTRICHTEGRDA IADDHCHEETAHGD BHRODRAVENENEG EYWDLSAMOLELHE ARTPVPRCBOLROR RHTOAAHCROWAGH CCANNORIAZEBRA HANYTAEKNINAWA 範例輸出 #1 DOLPHIN 範例輸入 #2 3 4 1 1 3 1 ROAR OINK WOOF 範例輸出 #2 ROW 解題思路 這題可以直接用For迴圈將字元加起來，需要注意的是要先判斷答案的字串是要求左到右平行、上到下垂直、還是左上到右下斜的。

題目敘述 本題採EOF方式收資料，每筆資料有一個正整數N，要求輸出f(N)的值。幾個f(N)的範例如下，題目要求自行判斷規律。 F ( 110  ) = 1 ,     F ( 163 ) = 1 ,   F ( 223 ) =  0 , F ( 119 ) = 1 ,      F ( 278 ) = 2 ,    F ( 821 ) = 2 。 範例輸入 #1 223 821 734 範例輸出 #1 0 2 0 解題思路 本題是考N這個數中每一個數字有多少個洞，舉例f(0)會是1、f(8)會是2。可以使用字串將N進行輸入之後使用if來判斷，範例程式碼中是使用Map來做判斷這樣可以直接將f(N)直接加到答案中。

題目敘述 本題採EOF方式收資料，每筆資料只有一行有兩個正整數a和b，當a和b都是0時代表測資結束停止收資料，a和b均小於10位數。要求輸出進行a+b的計算時總共進位了多少次 (輸出格式請見範例輸出)。 範例輸入 #1 123 456 555 555 123 594 0 0 範例輸出 #1 No carry operation. 3 carry operations. 1 carry operation. 解題思路 使用字串收數字，然後用最傳統的直式來做計算，可以先將兩個字串做反轉這樣跑For迴圈的時候可以從左跑到右。

題目敘述 每筆測資第一行有兩個正整數N和M，接下來會有一個N乘以M的二維陣列代表每個座標上的值。如果一個點他的曼哈頓距離內的點的值總和對10取餘數剛好為該點的數值，此為特殊位置。定義兩個點 (a, b) 和 (c, d) 的曼哈頓距離為 |a - c| + |b - d|。要求輸出二維陣列中有多少個特殊位置並輸出這個點的位置 (需經過排序)。 範例輸入 #1 1 8 1 2 3 4 5 6 7 8 範例輸出 #1 1 0 5 範例輸入 #2 2 3 5 2 3 4 5 6 範例輸出 #2 2 0 0  1 1 解題思路 判斷每個點的曼哈頓距離邊界 (上下左右)，但是不能超過陣列的邊界。從點延伸到曼哈頓距離邊界應該會是一個菱形的樣子，使用For迴圈將菱形中的數值加在一起後對10取餘數即可。座標的答案可以存放在Vector<Pair<int, int>>中，這樣可以直接用Sort排序。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有兩個整數代表x和y座標。最一開始的座標為(0, 0)，方向向右，只會有往左右走和往上下走的情況出現，不會有斜著走的情況出現。要求輸出走了N個點之後的左轉、右轉、和迴轉的次數。 範例輸入 #1 2 2 0 2 1 範例輸出 #1 1 0 0 範例輸入 #2 9   4 0 4 9 4 8 4 10 4 2 4 3 6 3 6 10 6 9 範例輸出 #2 2 1 5 解題思路 可以邊收資料邊做計算，判斷x和y的值和目前位置是增加還是減少來判斷要怎麼轉彎或者不用轉彎。

題目敘述 每筆測資第一行有一個正整數N，第二行會有N個正整數，代表每一個硬幣的幣值，第三行會有一個正整數代表要湊到的錢。要求輸出所有湊齊錢的幣種組合，需排序 (輸出格式請參照輸出範例)。 範例輸入 #1 3 1 5 10  17  範例輸出 #1 (2,1,1)  (2,3,0) (7,0,1) (7,2,0)  (12,1,0) (17,0,0)  解題思路 使用函式將每個幣值都加加看，如果等於要求的數量的話先將幣種組合存到一個二維陣列中，接下來直接用Sort排序這個二維陣列，需要注意的是存幣種組合的時候要判斷這個幣種組合是否已經有存到陣列中了，可以使用Map或Set來判斷。

題目敘述 本題採EOF方式收資料，每筆資料只有一個正整數N，要求輸出所有從1到N長度為N的字串，由大輸出到小。 範例輸入 #1 3 2 範例輸出 #1 321 312 231 213 132 123 21 12 解題思路 使用遞迴將每一種數字加到字串中，需要注意的是不能有重複的數字，可以使用Map或Set來做判斷。當判斷到字串長度為N時，將字串轉為整數並存到一個陣列中，一樣要先判斷是否已經有存過一樣的數字了。最後使用Sort排序陣列之後從最後一項往前輸出即可。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行字串，每個字串都是由小寫英文字母組成，無空格。要求輸出有多少對字串 (兩個) 加在一起之後切一半兩邊都是一樣的。 範例輸入 #1 3 a aba aaa 範例輸出 #1 1 範例輸入 #2 5 abyyyab y yy yyy yyyy 範例輸出 #2 3 解題思路 收字串的時候使用Map或Set來存哪些字串出現過。之後一個字串一個字串判斷，用For迴圈從0跑到字串的一半+1 (因為要Substring)，確認這個字串的第0個到第i個字元是否等於這個字串的最後i個字元，如果相等的話就判斷中間的字元有沒有在輸入時出現過，如果有的話答案就+1，最後輸出答案即可。如果Substring太多次的話可能會TLE所以需要優化一下避免太多次的Substring。

題目敘述 每筆測資第一行有一個正整數N，接下來要輸入一個N*N的二維字串。字串中的字元只會有兩種，'#' 代表路障不可走，'.' 代表路可走。每筆測資的起點都是 (2, 2)，以0-Base的說法會是 (1, 1)，終點是 (N-1, N-1)，同樣在0-Base來看會是 (N-2, N-2)。要求輸出最少要走幾步才會從起點走到終點，如果永遠無法走到終點則輸出 "No solution!" 。 範例輸入 #1 9 ######### #.......# #.#####.# #.......# ##.#.#### #..#.#..# #.##.##.# #.......# ######### 範例輸出 #1 13 解題思路 本題如果使用DFS會有TLE的情況出現，所以只能使用BFS的方式走，當沒有起點時就代表無法走到終點輸出No solution!。當走到終點時可以直接輸出目前的步數，因為先跑到的就會是最近距離。需要注意的是需要有一個Map來存已經走過的點，不能重複走到同一個點不然會有無限迴圈的情況出現。

題目敘述 每筆測資第一行有10個正整數，分別代表10個蘋果距離地面的高度 (單位：釐米)，第二行有一個正整數，代表陶陶伸手能觸碰到的高度  (單位：釐米) ，陶陶有一個長30釐米長的凳子。要求輸出陶陶能碰到幾顆蘋果。 範例輸入 #1 100 200 150 140 129 134 167 198 200 111 110 範例輸出 #1 5 解題思路 因為有一個30釐米長的凳子，所以在輸入蘋果高度的時候可以直接-30釐米。之後再一個一個判斷高度是否小於等於手能伸到的高度即可。

題目敘述 每筆測資有一個正整數N，要求輸出將1到N的所有數字隨機排序過後的結果。 範例輸入 #1 3 範例輸出 #1 2 1 3 範例輸入 #2 5 範例輸出 #2 5 3 2 1 4 解題思路 因為從1到N輸出也是一種隨機排序的可能性，所以直接使用For迴圈從1輸出到N即可。

題目敘述 每筆測資第一行有一個正整數T，代表接下來會有T組資料。每組資料第一行會有一個正整數N，借下來會有N行，每行有一個字串和兩個正整數，分別代表車廠名稱和其生產車輛的價格區間。再來會有一個正整數Q，接下來會有Q行，每行有一個正整數代表要查詢的價格。要求輸出查詢的價格區間的車廠，如果沒有或是超過一個車廠輸出UNDETERMINED，反之則輸出車廠的名稱。 範例輸入 #1 1 4 HONDA 10000 45000 PEUGEOT 12000 44000 BMW 30000 75900 CHEVROLET 7000 37000 4 60000 7500 5000 10000 範例輸出 #1 BMW CHEVROLET UNDETERMINED UNDETERMINED 解題思路 可以使用Vector<Pair>來將價格區間存起來，並且使用Map將車廠名稱利用Pair當索引值存起來。之後可以使用For迴圈一個一個做判斷即可，如果出現超過一個車廠直接Break迴圈節省時間。

題目敘述 本題採EOF方式收資料，每筆資料有一個字串和一個為0或1的數字，0代表這個題目 (題目名稱為字串) 沒有做過，1則是有做過。要求輸出還沒有做過的題目，順序由輸入順序輸出。 範例輸入 #1 a001 1 a002 1 a003 0 範例輸出 #1 a003 範例輸入 #2 b002 0 b003 0 b009 1 範例輸出 #2 b002 b003 範例輸入 #3 b002 0 b003 0 b002 0 b004 1 b004 1 b003 0 範例輸出 #3 b002 b003 解題思路 本題需要使用Map或Set來確認題目有沒有出現過了，因為會有重複的題號出現。

題目敘述 每筆測資第一行會有一個正整數N，接下來會有N筆資料，每筆資料會依序輸入一個字串 (代表學生名字)、一個整數 (代表學生班級)、一個整數 (代表學生座號)、和一個字串 (代表學生自介)。要求將班級和座號排序過後輸出班級、座號、名字、和自介 (格式請見範例輸出)。 範例輸入 #1 3 陳希臻 15 12 我喜歡吸貓 鄭允臻 14 27 我討厭陳芭樂 魏家琦 8 37 我其實是白家琦 範例輸出 #1 8 37 魏家琦 我其實是白家琦 14 27 鄭允臻 我討厭陳芭樂 15 12 陳希臻 我喜歡吸貓 解題思路 可以使用Pair和Map的方式將數字和字串分開來存，並用Pair來做排序，最後輸出排序過後的Pair和Map中的對應值即可。

題目敘述 本題採EOF方式收資料，每筆資料有四個正整數分別代表目前的時間和鬧鐘會響的的時間 (小時和分鐘)，當四個數字都等於0時停止收資料。要求輸出介於目前的時間和鬧鐘設定的時間相差幾分鐘，有些資料會換日。 範例輸入 #1 1 5 3 5 23 59 0 34 21 33 21 10 0 0 0 0 範例輸出 #1 120 35 1417 解題思路 可以將兩個時間都換算成最小的單位 (分鐘) ，當目前的時間大於鬧鐘的時間的時候代表會換日，所以鬧鐘的時間要加一天 (24*60) ，最後輸出鬧鐘的分鐘數減掉目前時間的分鐘數即可。

題目敘述 每筆測資有三個整數，分別為數列的起點、終點、和等差值。要求輸出從起點到終點的等差數列 (可有負數)。 範例輸入 #1 1 9 2 範例輸出 #1 1 3 5 7 9 解題思路 使用While迴圈，終止條件為起點等於終點，不可使用小於因為有負數的可能性。

題目敘述   題目採EOF方式收資料，每個資料有一個字串，輸入完之後要輸出這個字串在之前的輸入中是否有輸入過，如果有的話就輸出1，沒有的話就輸出0。 範例輸入 #1 CHUANG HAOYU LIKE A FROG A FROG LIKE HAOYU CHUANG 範例輸出 #1 0 0 0 0 0 1 1 1 1 1 解題思路 本題的時間很緊，所以要使用Unorder_Map來做判斷會比較省時間，還需要做Cin的優化。

題目敘述 題目採EOF方式收資料，每筆資料只有一個正整數代表顧客評了幾顆星。要求輸出每個星級的數量和該星級的長條圖 (格式請見範例輸出)，最後輸出平均值，小數點四捨五入到第四位。 範例輸入 #1 4 5 3 4 2 4 3 5 2 1 3 2 4 3 2 4 3 3 2 4 3 3 5 3 1 4 3 2 4 5 4 3 4 3 3 4 3 0 範例輸出 #1 5 ( 4) |==== 4 (11) |=========== 3 (14) |============== 2 ( 6) |====== 1 ( 2) |== Average rating: 3.2432 解題思路 可以使用MAP來存放資料，輸出平均值的部份可以用printf的方式來做只到第四位的輸出。

題目敘述 題目採EOF方式收資料，每一筆資料有一行字串，要求輸出所有字元位於鍵盤上左邊的按鍵，Q、A、Z、`，這四個字元和空白除外。 範例輸入 #1 O S, GOMR YPFSU/ URD. ,U [JPMR MI,NRT OD 8346333 範例輸出 #1 I AM FINE TODAY. YES, MY PHONE NUMBER IS 7235222 解題思路 可以使用Map來建檔，需要注意的是 \ 和 ' 都屬於特殊字元需要用另一個寫法，\ 要寫成 \\，' 要寫成 \'。

題目敘述 每筆測資第一行有一個正整數N，代表接下來會有N筆資料。每筆資料第一行有兩個正整數M和K，代表醫生開了M種藥和需要服用K個藥物才會好起來，接下來會有M行，每行會有一個字串代表藥物的名稱及一個正整數代表這個藥物服用的頻率，先輸入的藥物的優先級就越高。要求輸出每次服用藥物的時間和藥物名稱直到病情好起來為止，如果有同一時間需要服用超過一種藥物時，優先輸出優先級較高的藥物。 範例輸入 #1 1 2 5 Acetaminophen 20 Loratadine 30 範例輸出 #1 20 Acetaminophen 30 Loratadine 40 Acetaminophen 60 Acetaminophen 60 Loratadine 解題思路 使用Vector和Pair將藥物的名稱及服用頻率存起來，並用While迴圈來判斷目前的時間是否有需要服用的藥物 (可以被服用頻率整除)。需要注意的是只要服用了一種藥物就需要判斷目前服用的藥物數量是否有等於K，如果有的話就需要將迴圈Break掉。

題目敘述 每筆資料第一行有一個正整數N，接下來第二行會有N個整數，要求輸出數列的前綴和。 範例輸入 #1 5 1 2 3 4 5 範例輸出 #1 1 3 6 10 15 解題思路 可以使用For迴圈來收資料，並且使用一個變數來存目前的前綴和。需要注意本題需使用Long Long Int。

題目敘述 每個測資都只有10行，前九行每行有一個正整數N，接下來會有N個字串，分別代表這一個打者每一次打球的結果。每次打擊都是從第一位打者打到第九位打者接下來回到第一位。最後一行有一個正整數B代表要輸出當出局數累計到B時的分數，每三次出局的時候所有壘包都會清空。 以下為每個字串的意思： (1) 安打：以1B,2B,3B和HR 分別代表一壘打、二壘打、三壘打和全（四）壘打。 (2) 出局：以 FO,GO和 SO表示。 範例輸入 #1 5 1B 1B FO GO 1B 5 1B 2B FO FO SO 4 SO HR SO 1B 4 FO FO FO HR 4 1B 1B 1B 1B 4 GO GO 3B GO 4 1B GO GO SO 4 SO GO 2B 2B 4 3B GO GO FO 3 範例輸出 #1 0 範例輸入 #2 5 1B 1B FO GO 1B 5 1B 2B FO FO SO 4 SO HR SO 1B 4 FO FO FO HR 4 1B 1B 1B 1B 4 GO GO 3B GO 4 1B GO GO SO 4 SO GO 2B 2B 4 3B GO GO FO 6 範例輸出 #2 5 解題思路 將資料收完之後可以判斷現在的打者是幾壘安打，然後從第三壘開始判斷。假如現在是一壘安打的話三壘的人就會跑回本壘，分數就會+1，然後三壘會清空。然後再來判斷二壘，如果二壘有人的話就會跑到三壘然後二壘清空，以此類推。需要注意的是當出局數為三的倍數時需清掉所有壘上的人。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N筆資料。每筆資料有兩行，每行有7個為0或是1的整數，0代表平聲，1代表仄 聲。要求輸出資料中的對聯有沒有符合下列規則，如果有沒有符合的就輸出該規則的編號，如果三個規則都有符合則輸出None。 七言對聯有三個限制： A: 二四不同二六同：每一句第二、四個字必須不同平仄，而第二、六個字必須相同平仄 B: 仄起平收：第一句的結尾必須為仄聲，第二句的結尾必須為平聲 C: 上下相對：第一、二句的第二、四、六個字平仄必須不同 範例輸入 #1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 範例輸出 #1 AC 範例輸入 #2 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 範例輸出 #2 None 範例輸入 #3 2 0 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 範例輸出 #3 AB ABC 解題思路 可以使用Vector先將兩句對聯存起來並使用Index的方式來做判斷，依照題目的規則去做判斷即可。

題目敘述 每筆測資第一行有一個正整數N，借下來會有N筆資料，每筆資料有三個正整數E、F、C。E代表一開始有的空瓶子，F代表撿到的空瓶子，C代表需要多少空瓶子可以換一瓶汽水。要求輸出最多可以喝到幾瓶汽水。 範例輸入 #1 2 9 0 3 5 5 2 範例輸出 #1 4 9 解題思路 本題可以使用While迴圈來做每一次的判斷，所有空瓶子的數量 (初始值) 就是E+F，需要注意的是，當換了一瓶汽水之後就會喝掉，所以空瓶子的數量也要+1。

題目敘述 每筆資料第一行有一個正整數N，借下來會有N行每行有一個字串。要求輸出在可以有一個字元寫錯的情況下這是什麼數字，答案只有1、2、3，字串長度不會有改變。 範例輸入 3 owe too theee 範例輸出 1 2 3 解題思路 3這個答案可以直接判斷字串長度是否為5直接輸出。剩下的兩個其實組合方式只有6種，將這六種寫成if判斷式即可。

題目敘述 題目採EOF收資料，每筆資料有一個正整數，要求將該數的所有質因數的和。 例子： 6 = 2 x 3，輸出 2 + 3 = 5 8 = 2 x 2 x 2，輸出 2 + 2 + 2 = 6 範例輸入 19 32 範例輸出 19 10 解題思路 使用For迴圈判斷輸入整數的質數為多少 (只需要判斷到輸入測資的根號即可)，不需要使用scanf/printf不會TLE，但是建議使用cin加速。依題目測資判斷1不判斷為質數，如果輸入資料為質數，則直接輸出該質數即可。

題目敘述 每筆資料第一行有一個正整數N，下一行會有N個整數。要求輸出此數列中的「最強者」。 最強者定義： 假設現在有 N 人，我們可以分為左半邊 N/2 人和右半邊 N/2 人。 同樣地，對於左半邊 N/2 人，可以繼續平分為 N/4 人和 N/4 人， 直到無法再平分，也就是只剩下 1 人為止。 對於只有 1 人的區間，那人當然就是該區間內的最強者。 對於其他區間，則在找到左半邊最強者和右半邊最強者後，就可以簡單地對兩數字比較，以得到本身區間最強者。 但是強者的定義時常在變化，有時以小博大，有時以大搏小，兩者交替出現。 也就是假設這回合大者優先，則下回合會是小者優先，下下回合則又回到大者優先，依序下去...... 這邊我們預設最初 N 人的區間為大者優先， 因此所劃分出的 N/2, N/2 區間將為小者優先，繼續劃分出的 N/4, N/4, N/4, N/4 則又回到大者優先...... 範例圖： 範例輸入 #1 8 1 2 3 4 5 6 7 8 範例輸出 #1 6 解題思路 使用遞迴的方式將數量一直切成一半，當數列只剩下一個數字時 (左界線＝右界線)，就return 目前的數字。大小的判斷可以每次進入函式時將一個布林值反轉並且return 最大值或最小值。

題目敘述 每筆資料只有一個正整數N，N不會超過65535。要求輸出N所有因數 (不包含N自己) 的和。 例如：6的因數有1、2、3、6 --> 1+2+3 = 6。 範例輸入 #1 6 範例輸出 #1 6 範例輸入 #2 12 範例輸出 #2 16 解題思路 使用For迴圈從1跑到N-1 (因為不能包含N自己)，因為數字不大所以可以直接一個一個判斷所有N的因數並將所有因數加在一起，最後輸出因數和即可。