技藝編程

題目敘述 每筆資料只有一個正整數N，要求輸出第N天時有幾個病毒，第一天時的病毒量為1。 病毒計算公式如下： 範例輸入 #1 2 範例輸出 #1 4 範例輸入 #2 10 範例輸出 #2 340 解題思路 可以使用函式回傳數值的方式做遞迴，終止條件是當N=1時就回傳1。

題目敘述 題目採EOF方式收資料，每筆資料有一個正整數N (N最大可達1000位數)，當N=0時停止收資料。要求輸出N是否為11的倍數 (輸出格式請見範例輸出)。 範例輸入 #1 112233 30800 2937 323455693 5038297 112234 0 範例輸出 #1 112233 is a multiple of 11. 30800 is a multiple of 11. 2937 is a multiple of 11. 323455693 is a multiple of 11. 5038297 is a multiple of 11. 112234 is not a multiple of 11. 解題思路 本題的數字會超過long long int的範圍，所以要使用字串的方式將N收進來。可以使用以下公式來判斷N是否為11的倍數：如果奇數位數的數字和與偶數位數的數字和的差是11的倍數的會N即為11的倍數。可以使用For迴圈將每一個位數的數字都做相加並在For迴圈結束後進行判斷。

題目敘述 每筆輸入第一行有一個正整數N，接下來會有N筆資料。每筆資料有兩行，第一行有一個正整數M，第二行有M個整數。要求輸出將第二行的數字進行排序時需要swap (交換) 幾次。 範例輸入 #1 3 3 1 3 2 4 4 3 2 1 2 2 1 範例輸出 #1 Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps. 解題思路 可以使用Bubble Sort (氣泡排序法)，每次進行Swap的時候就將答案的變數+1，最後輸出Swap的次數即可。

題目敘述 每筆輸入第一行有一個正整數N，接下來會有N行，每行會有兩個用空白隔開的未含空格的字串a和b，代表a是b的小孩、b是a的父母。收完資料之後還有一行，這一行有兩個用空白隔開的未含空格的字串c和d，要求輸出c和d的輩份關係，如果老一輩就-1，如果晚一輩就+1，如果是同輩就是0。 範例輸入 #1 3 Jacob Isaac Isaac Abraham Ishmael Abraham Jacob Ishmael 範例輸出 #1 -1 範例輸入 #2 3 A ABC B ABC C ABC A C 範例輸出 #2 0 範例輸入 #3 4 me dad dad grand-dad son me grand-son son grand-dad grand-son 範例輸出 #3 4 解題思路 本題類似於樹狀圖的概念，可以創建一個struct，裡面存名字、長輩、和晚輩。然後再利用Map來將名字當成Key把這些struct存進來。最後再使用BFS的方式從要找的名字開始往上和往下找，要注意的是，需要再使用一個Map來紀錄目前這個名字是否有被走過了以免進行重複的運算。

題目敘述 本題採EOF方式收資料，每筆資料有兩個整數a和b。座標平面上，當螞蟻在(a,b)時，可隨機移動到點(a-1,b), (a,b-1), 或(a-1,b-1)之中的一點，且移動到上述任一點的機率均為1/3，又接下來每次移動都與前次移動無關。現有一螞蟻從 (x,y) 開始移動，直到第一次遇到任意座標軸即停止移動，請問此螞蟻最後一次停止的點不是在原點 (0,0) 機率為何? 範例輸入 #1 3 3 2 2 1 1 範例輸出 #1 70/81 22/27 2/3 解題思路 因為使用分數較難運算，所以可以將原點的機率 (也就是100%或1) 乘以3的a+b次方。可以使用二維陣列來存每個點的移動機率，使用雙For迴圈將每個點都走過一遍。答案的分子就是原本的點-(0, 0)的點的機率，分母就是原來的點的機率。最後將分數約分到最簡分數再輸出即可。

題目敘述 每筆資料只有一行正整數N，要求輸出N行的楊輝三角形 (輸出格式如範例所示)。 範例輸入 #1 5 範例輸出 #1 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 解題思路 可以使用陣列來存取上一行的資料來做這一行的運算。第一行因為都是一個1所以可以直接在For迴圈外面push_back一個1進去+輸出即可。使用For迴圈從第二行跑到第N行，裡面再放一個For迴圈，第幾行就要輸出幾個數字。在第二個For迴圈裡判斷目前是不是跑到第一個數字或是最後一個數字，如果是的話就是push_back一個1，如果不是的話就將上一行的這個位置的數字加上上一行的這個位置-1的數字push_back，最後再進行輸出＋換行即可。

題目敘述 題目採EOF方式收資料，每筆資料會有兩行字串，當第一個字串為「STOP!!」時停止收資料。要求輸出如果將兩個字串排序過後可不可以變成一樣的字串，可以的話則輸出「yes」，反之則輸出「no」。 範例輸入 e83k 38ek asdfghjkl;' ';lkjhgfdsa 1234 4521 _01=1 _=110 SToP!! stop!! STOP!! 範例輸出 yes yes no yes no 解題思路 本題需使用cin優化/scanf才不會TLE (cin優化詳情請見範例程式碼)，另外收到兩組字串過後可以先判斷兩個字串的長度是否相同，如果不相同的話直接輸出no節省時間。可以使用For迴圈將每個字串中的字元做處理，使用一個Map存每個字元出現的次數。假設兩個字串的名稱叫做A和B，把A的每個字元的Map值做+1、把B的每個字元的Map值做-1。之後使用 for (auto it:MAP) 來將Map中的資料做判斷，使用for (auto it:MAP) 的時候it這個變數會變成一個pair，所以只要判斷it.second是否為0，如果有不是0的話就輸出no並將For迴圈break掉節省時間，如果都是0的話就輸出yes。

題目敘述 每筆輸入有一行整數，要求將每個出現的數字由大到小排序 (使用該數字的出現次數排序) 並輸出，如該數字沒有出現則不需輸出。 範例輸入 #1 2425264426558 範例輸出 #1 2 4 5 6 8 範例輸入 #2 1234567891011121314 範例輸出 #2 1 2 3 4 0 5 6 7 8 9 解題思路 使用「EOF」收「字元」的方式收資料，這樣子一次只會收一個字元不需要使用long long int或是string+stringstream來處理資料，當收到字元時使用MAP將該數字出現的次數+1。接下來可以使用while (true)迴圈來做輸出判定。每次while迴圈中跑一個For迴圈來確認目前MAP中最大值的數字為多少，並將其輸出且把該數字的MAP值設為0。當所有大於0的MAP值都輸出過之後就將While迴圈break掉，最後換行即可。

題目敘述 每筆資料有兩個數字N和P，N代表一組有幾個人，P代表參賽選手的戰力 (均為個位數)。分組的機制是由右往左排，不一定每一組都會有N個人。要求輸出戰力總和最高的組別的編號 (由右往左分組的話為第幾組) 和戰力總和。 範例輸入 #1 1 369 範例輸出 #1 1 9 範例輸入 #2 2 193426 範例輸出 #2 3 10 範例輸入 #3 5 10121315 範例輸出 #3 1 12 範例輸入 #4 4 12344321 範例輸出 #4 2 10 解題思路 可以將P使用字串的方式存起來，因為題目有講最多不會超過9位選手，所以可以使用reverse不用擔心會TLE，將字串反轉之後就使用For迴圈將每一個字元做判斷並且找出最大戰力總和的組別。

題目敘述 每筆輸入有一個字串，要求輸出此字串是否為迴文，且該字串只能包含AHIMOTUVWXY。如有任一項沒有達到，則輸出No，反之則輸出Yes。 範例輸入 #1 A 範例輸出 #1 Yes 範例輸入 #2 ABA 範例輸出 #2 No 範例輸入 #3 HOHOH 範例輸出 #3 Yes 解題思路 可以使用EOF的方式一個字元一個字元來收並使用Map或if來判斷該字元是否為AHIMOTUVWXY的其中一個，需要注意的是，就算判斷到該字元不屬於AHIMOTUVWXY也需要把資料讀完才能輸出No，所以可以使用一個布林值來存能不能直接輸出No。如果為AHIMOTUVWXY的其中一個字元的話就將其字元加到一個string的變數中待EOF結束後做迴文的判斷。迴文的判定可以使用Algorithm中的reverse來判斷從右到左和從左到右的字串是否為一樣的。

題目敘述 每筆資料第一行有一個正整數N，第二行會有N個正整數代表每一隻獅子的身高，第三行會有N個正整數代表每一隻獅子的體重。要求輸出身高*體重之後最小值的獅子的身高與體重。 範例輸入 #1 2 145 34 21 55 範例輸出 #1 34 55 範例輸入 #2 4 361 619 555 855 419 758 549 240 範例輸出 #2 361 419 範例輸入 #3 5 17 100 40 111 68 157 151 25 173 197 範例輸出 #3 40 25 解題思路 使用陣列/Vector先將身高的數值記錄下來，在收體重的資料時直接做乘法並判斷最小值。可以先把第一個獅子的體重設為最小值變數的初始值。

題目敘述 每筆輸入有一個字串，要求輸出這個字串是星期幾的英文。星期日為0、星期一為1，以此類推。如果字串拼字有誤，則輸出「error」。 範例輸入 #1 Sunday 範例輸出 #1 0 範例輸入 #2 Twosday 範例輸出 #2 error 解題思路 使用Map將每個日期的索引值存起來，如果讀到的字串在Map中沒有值的話就輸出error，反之則輸出Map的值。

題目敘述 本題採EOF方式收資料，每筆資料第一行會有兩個正整數N和M，當N和M等於0時停止收資料。接下來會有N行，每行有一個英文單字，接下來會有一行包含M個以空格分開的正整數。要求將N個英文單字組成一整個字串時輸出每個數字給的字串位置的字元。 範例輸入 9 8 the quick brown fox jumps over the lazy dog 33 11 34 19 21 33 30 32 0 0 範例輸出 doomsday 解題思路 將所有英文單字加到一個字串之後，在收數字時就將字串的那一位-1 (因為測資的數字是1-Based) 輸出即可，最後換行。

題目敘述 每筆資料第一行有一個正整數N，第二行有N個整數。要求輸出有幾個不重複的數字並將那些數字排序後輸出 (輸出格式請參照輸出範例)。 範例輸入 10 20 40 32 67 40 20 89 300 400 15 範例輸出 8 15 20 32 40 67 89 300 400 解題思路 可以使用Map來判斷該數有沒有出現過，如果有出現過的話就不要塞到陣列/Vector中，沒有出現過的話就塞到陣列裡並把Map值+1。最後輸出陣列大小還有sort之後的陣列幾可。

題目敘述 本題採EOF方式收資料，每筆資料第一行有兩個正整數N和M，第二行會有N個數字代表數列中的數。接下來會有M行，每行會有一個字元和兩個整數A和B。當字元為C時，將數列中第A個位置的資料改為B。當字元為P時，如果位置A到B的乘積為正的話輸出+，負的話輸出-，0的話則輸出0。 範例輸入 #1 4 6 -2 6 0 -1 C 1 10 P 1 4 C 3 7 P 2 2 C 4 -5 P 1 4 5 9 1 5 -2 4 3 P 1 2 P 1 5 C 4 -5 P 1 5 P 4 5 C 3 0 P 1 5 C 4 -5 C 4 -5 範例輸出 #1 0+- +-+-0 解題思路 建立線段樹的資料結構來更改資料及確認區段的乘積。

題目敘述 每筆輸入只有兩個正整數A和B，分別代表小時和分鐘 (輸入和判斷採24小時制)。要求輸出如果輸入的時間介於7:30和17:00 (包含7:30和17:00) 的話輸出At School，反之則輸出Off School。 範例輸入 17 00 範例輸出 Off School 解題思路 使用if來判斷輸入的時間使否為上學時間的區間即可 (詳情請見範例程式碼)。

題目敘述 每筆輸入第一行有一個正整數N，第二行會有N個數字代表從第一天到第N天每天購買的饅頭數量。第一天一個饅頭只要一元，第二天就要二元，第三天要賣三元，以此類推。要求輸出總夠花費多少錢。 範例輸入 5 1 2 3 4 5 範例輸出 55 解題思路 使用For迴圈邊收資料邊加，For迴圈從1跑到N，將收到的資料乘以i並且加到加總變數裡，最後再輸出答案變數即可。

題目敘述 每筆輸入第一行有一個正整數N，接下來有N行，每行第一個數字M為接下來會有多少個數字要做輸入。要求輸出這M個數的連續最大和。 範例輸入 3 5 1 2 -3 4 5 5 1 2 3 4 5 6 10 -5 7 6 -1 -3 範例輸出 9 15 18 解題思路 使用For迴圈將資料收到一個陣列/Vector中。使用一個For迴圈來設定現在要加總的起點，裡面再放一個For迴圈從上一個For迴圈中的值跑到M結束，每次都將數列中的數字加到一個變數中，並且每次都進行最大值的比對。最後將最大值的變數輸出即可。

題目敘述 每筆輸入第一行有一個正整數N，接下來會有N行，每行第一個正整數M代表接下來會有幾個數字要做輸入。要求輸出每筆資料的平均值 (四捨五入至小數點第二位)。 範例輸入 2 5 2 4 6 8 10 3 52 30 61 範例輸出 6.00 47.67 解題思路 使用For迴圈將數字都加到一個變數中，再把sum/M的值存到一個double變數中。需要注意的是，sum和M這兩個變數可以使用double來宣告這樣子就不需要在計算平均值時做轉型的動作。計算完之後可以使用stdio.h中的printf(%.2f\n, ans)來做四捨五入到第二位的輸出。

題目敘述 題目採EOF方式收資料，每筆資料有三個正整數，分別代表餅乾、巧克力、和蛋糕。每10個餅乾和2個蛋糕就可以多贈送一個巧克力。要求輸出最後的餅乾、巧克力、和蛋糕的數量 (詳細輸出格式請參照輸出範例)。 範例輸入 12 6 3 範例輸出 12 個餅乾，7 盒巧克力，3 個蛋糕。 解題思路 可以使用一個While迴圈，終止的條件就是當餅乾小於10或蛋糕小於2兩個情況只要一個有發生就終止迴圈。迴圈中只要將巧克力的數量+1、餅乾-10、蛋糕-2就可以了。需要注意的是餅乾和蛋糕的原始數量需存在其他兩個不會做加減的變數中才行。最後只要輸出原始的餅乾＋蛋糕值和加總完的巧克力數量即可。

題目敘述 本題採EOF方式收資料，每筆資料有一個整數N，當N為0時停止收資料。要求輸出大於0、整數、不可以被 7 整除、小於N的數字。 範例輸入 5 10 20 0 範例輸出 1 2 3 4 1 2 3 4 5 6 8 9 1 2 3 4 5 6 8 9 10 11 12 13 15 16 17 18 19 解題思路 使用For迴圈並判斷跑到的數字是否能被7整除，如果不行的話就輸出，反之則continue。

題目敘述 每筆輸入只有一個大於0的正整數N，要求輸出 F(N)。F(N) 解釋如下： 如果N = 1，則 F(N) = 1。 如果N是偶數，則 F(N) = F(N/2)。 如果N是奇數且不等於1時，F(N) = F(N+1) + F(N-1)。 範例輸入 6 範例輸出 2 解題思路 本題可以寫一個遞迴函式，終止的條件是當N = 1時就return N，然後將偶數及奇數的判斷式寫好然後cout遞迴(N)就可以了 (詳情請見範例程式碼)。

題目敘述 每筆資料第一行有四個正整數P、Q、R、M，下一行會有P個整數 (0或1) 代表輸入端口的數值，接下來會有Q個正整數代表邏輯端的判斷類型 (1 為 AND、2 為 OR、3 為 XOR、4 為 NOT)。最後會有M行，每行有兩個正整數A和B，代表從A點到B點有一條線。點的命名方式可以餐考以下圖片，圖片為範例輸入/輸出 #1的解析圖。 要求輸出延遲的秒數 (會在解題思路中解釋) 和輸出端點的值。 範例輸入 #1 4 5 4 13 1 0 1 0 1 2 3 4 1 1 5 2 5 2 6 3 6 3 7 4 7 4 8 5 10 6 9 6 11 7 9 8 13 9 12 範例輸出 #1 2 0 1 1 1 範例輸入 #2 5 6 4 15 1 1 0 1 0 2 1 3 4 1 3 1 6 2 7 7 13 7 6 3 7 3 8 4 8 5 9 8 10 9 10 10 14 10 11 9 11 6 12 11 15 範例輸出 #2 3 1 0 1 0 解題思路 可以使用一個struct來存取每一個端點/邏輯端的數值，將資料都收到struct中之後，使用BFS先跑輸入端點，將輸入端點的終點值的起點值存成目前的數字。經過判斷已經可以做邏輯端的運算後就可以將運算過後的值放到struct中存輸出值的變數。延遲的部分只需判斷跑了幾次的BFS再-1即可。

題目敘述 每筆資料第一行有三個正整數M、N、K，接下來要收一個M*N的二維字元陣列，之後的一行有K個整數，代表要往哪裡走。題目的字元結構是採蜂巢形，下面有圖片做參考。0 是往右上; 1 是往右邊; 2 是往右下; 3 是往左下; 4 是往左邊; 5 是往左上。 要求每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數 (大小寫相異)，若經過時碰到牆壁該行動會停在原地，屆時要輸出目前該位置的字元。 範例輸入 #1 2 4 5 TyuI ABaB 0 1 2 3 0 範例輸出 #1 Tyaau 4 範例輸入 #2 4 6 11 rMmnis LRveEX ZexDoc HAdbHA 0 1 5 1 1 0 3 0 0 1 0 範例輸出 #2 ZeLRvmvmmnn 7 解題思路 本題比較複雜的地方是因為題目的結構是蜂巢狀，但是收資料的時候是採正方形的方式。但是可以理解為：右上的時候x和y值的變化為 (0, -1)、右邊的時候為 (1, 0)、右下的時候為 (1, 1)、左下的時候為 (0, 1)、左邊的時候為 (-1, 0)、左上的時候為 (-1, -1)。如果不理解的話可以拿範例一的資料用畫的方式畫畫看就會大概知道這個概念。需要注意的是每次行走時都需要判斷這樣子走會不會超出陣列的邊界。輸出次數的部分可以使用Map來存已經出現過的字元。

題目敘述 每筆資料第一行有一個正整數N，接下來會有N行，每行有兩個整數a和b。要求將a和b的平方和做排序後將第二大的平方和的a和b做輸出。 範例輸入 #1 3 3 1 5 2 1 4 範例輸出 #1 1 4 範例輸入 #2 6 6 6 1 3 8 6 5 4 2 8 7 2 範例輸出 #2 6 6 範例輸入 #3 5 34 35 84 32 39 79 59 89 59 31 範例輸出 #3 84 32 解題思路 可以將a和b的平方和存到一個陣列/Vector中，然後使用Map將平方和作為Key，存的資料可以使用Pair來存，這樣就可以一次存兩個數字。使用Sort將陣列中的資料做排序後只要輸出倒數第二個位子的Map值即可。

題目敘述 每筆輸入都只有一個整數N，要求輸出絕對值的N。 範例輸入 -5 範例輸出 5 解題思路 使用abs(N)直接輸出即可。

題目敘述 題目採EOF方式收資料，每筆資料有兩個正整數N和M，當N和M都等於-1時停止收資料。要求輸出從N到M需要加幾次1或減幾次1 (當0減1時會自動變成99)。 範例輸入 3 9 0 99 12 27 -1 -1 範例輸出 6 1 15 解題思路 將加1跟減1的值都算出來並比較哪邊比較小並輸出較小的值。

題目敘述 題目採EOF方式收資料，每筆資料有一行字串，當字串是'#'時停止收資料。判斷該字串的語言為何 (詳情請見範例測資)。 範例輸入 HELLO HOLA HALLO BONJOUR CIAO ZDRAVSTVUJTE # 範例輸出 Case 1: ENGLISH Case 2: SPANISH Case 3: GERMAN Case 4: FRENCH Case 5: ITALIAN Case 6: RUSSIAN 解題思路 使用if來判斷該字串的語言為何，可以使用一個int變數放在EOF外面來確認目前是第幾個Case。

題目敘述 題目採EOF方式收資料，每筆資料有一行由數字和字母組成的字串 (無空格)。要求輸出經過特殊排序規則後的結果，排序規則如下： 字母的部分原地反轉。 數字的部分依數字於整個字串的位置反轉。 範例輸入 123abc456de7fgh890i FGwxjgdoCaT24txLeGkehc958KP 範例輸出 098cba765ed4hgf321i TaCodgjxwGF85chekGeLxt942PK 解題思路 使用For迴圈和isalpha()函式一個字元一個字元進行判定。因為字母的部分是按照區塊進行排序，所以可以先宣告一個空的字串來存字母，當讀到字母時就將當前字母加到剛剛宣告的字串。如果是讀到數字的話就是確認存字母的字串是否為空，如果不是空的話就先reverse字串之後存到一個存字母陣列/Vector中，然後再將數字存到存數字的陣列/Vector中，兩邊分開處理。For迴圈結束之後使用reverse將數字的陣列做反轉，字母的不需要反轉。然後再使用一個For迴圈一樣跑輸入進來的字串做字元判定，當讀到數字時就輸出數字陣列中的第一個資料，然後就使用erase將第一個資料刪除。當讀到字母時也是將字母陣列中的第一個字串做輸出，但是在做erase之前要先把i+=alpha[0].length()-1，這樣子For迴圈下一次就會直接跳到這個連續字母的結尾的下一個資料，把i加完之後才能將字母陣列中的第一個資料做刪除。

題目敘述 題目採EOF方式收資料，每筆資料都有一行若干個整數用逗號隔開 (詳情請見輸入範例)。要求只將數列中的偶數進行排序並輸出，奇數維持不動 (詳情請見輸出範例)。 範例輸入 1,8,9,2,7 範例輸出 1,2,9,8,7 解題思路 使用字串將每一筆資料收進來，並且使用For迴圈來判斷每一個字元，如果目前的字元為逗號的話則將上一個逗號到這一個逗號的字串/字元塞到一個陣列/Vector中。如果這個數字為偶數的話則在把這個數字塞到原本的陣列的同時再塞到一個只有偶數的陣列/Vector中，並且要紀錄這個偶數目前在陣列中的位置，範例程式碼使用Map來紀錄。將偶數的陣列用algorithm的sort進行排序過後，跑一個原本陣列的For迴圈，當判定到目前的i是偶數的話就輸出偶數陣列的第一個資料，輸出完之後就使用erase (使用方式請見範例程式碼) 將第一個資料消除掉，如果目前的i不是偶數的話就輸出原本陣列中的資料。需要注意的是，輸出時是用逗點而不是空格隔開資料，所以最後一筆資料輸出過後不能再輸出一個逗號，這個需要做另外的判斷。

題目敘述 每筆輸入有兩個正整數N和M，要求輸出N到M之間 (包含N和M) 的「阿姆斯壯數」。如果該區間沒有阿姆斯壯數的話請輸出none (詳情請見輸入/輸出範例)。 阿姆斯壯數解釋：一個N位數的整數，它的所有位數的N次方和恰好等於自己。 例子：1634 = 1^4 + 6^4 + 3^4 + 4^4 範例輸入 #1 100 999 範例輸出 #1 153 370 371 407 範例輸入 #2 10 99 範例輸出 #2 none 解題思路 使用For迴圈從N跑到M依依檢查。可以將數字轉換成字串來進行阿姆斯壯數的判斷 (詳情請見範例程式碼)。將得到的阿姆斯壯數存到一個陣列/Vector中，判斷如果Vector的Size為0則輸出none，反之則將Vector中的資料輸出。

題目敘述 每筆輸入有一個正整數N。要求輸出如果班上有N個人最低採購鉛筆的金額為多少。 一打鉛筆 (12支) 50元，一支鉛筆5元。 範例輸入 42 範例輸出 180 解題思路 可以將N除以12的答案*50，然後加上N%12的答案*5，即可獲得答案。