技藝編程

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有四個正整數，分別代表起點和終點的x和y座標。根據笛卡爾坐標系，需要按照以下所示的箭頭路徑從一個圓圈移動到另一個圓圈。 例如，要從 (0, 3) 到 (3, 0)，您必須經過兩個中間圓 (1, 2) 和 (2, 1)。 所以，在這種情況下，所需的總步數是 2 + 1 = 3。 要求輸出從起點走到終點需要走幾步。 範例輸入 #1 3 0 0 0 1 0 0 1 0 0 0 0 2 範例輸出 #1 Case 1: 1 Case 2: 2 Case 3: 3 解題思路 如果把步數標出來的話，可以發現Y軸 (橫軸) 的步數是 0 --> 1 --> 3 --> 5 --> 9，以此類推。舉例來說，當x+y等於2的時候，可以發現這些點都落在 (0, 2) 這個點的斜線上，更可以發現 (1, 1) 這個點是 (0, 2) 的步數＋1，也就是其x座標。同理，(2, 0) 的步數就是 (0, 2) 的步數＋2。 可以先設定一個陣列，並將 0、1、3、6、10．．．等數字存放到Y座標 (橫軸) 的位置上。收資料的時候判斷x+y是多少就找這個位置的步數然後加上x座標的值。

題目敘述 每筆測資第一行有一個正整數T，代表接下來會有T筆資料。每筆資料第一行會有一個正整數N，下一行會有N個正整數代表N個商品的價錢。商品是買二送一，省下來的錢會是最便宜的那個商品之價錢。要求輸出可以省下的最多費用。 範例輸入 #1 1 6 400 100 200 350 300 250 範例輸出 #1 400 解題思路 將每個商品的價錢收到一個Vector或陣列中，收完之後使用Sort來排序。再來跑For迴圈，從最大跑到最小，以每三個為單位，並將目前位置減2的價錢加到答案中。

題目敘述 每筆測資有兩個正整數N和M，代表有N個人圍成一個圓圈，以及要傳球M次。每次傳球只能傳給左右兩邊的人。要求輸出有幾種傳球方法可以傳M次之後傳回第一個人手上。 範例輸入 #1 3 3  範例輸出 #1 2 解題思路 使用BFS來處理，每一次計算球要傳給誰，並且將每個起點的次數進行加總，可以利用Map來做存取，並且每次跑BFS的時候都回傳這個Map，當BFS的次數等於M時就將第一個人的Map值輸出。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每一行會有四個正整數代表四邊形的四個邊長。要求輸出是否是「正方形」、「長方形」、「四邊形」、或是「無法形成四邊形」。 範例輸入 #1 4 10 8 7 6 9 1 9 1 29 29 29 29 5 12 30 7 範例輸出 #1 quadrangle rectangle square banana 解題思路 將四個邊長收到Vector中，並且進行排序。 正方形：四邊等長 長方形：前兩邊相等、後兩邊相等 四邊形：前三個邊的和「大於」第四個邊 非四邊形：Else

題目敘述 每筆測資第一行有一個正整數T，接下來會有T行，每行會有三個正整數，代表三個人的薪資。要求輸出排序後中間的人的薪資。 範例輸入 #1 3 1000 2000 3000 3000 2500 1500 1500 1200 1800 範例輸出 #1 Case 1: 2000 Case 2: 2500 Case 3: 1500 解題思路 將三個數字收到Vector或陣列中，然後進行排序，再將第一個位置的資料 (中間的資料) 輸出即可。

題目敘述 每筆測資第一行有一個正整數T，接下來會有T行，每行會有一個正整數N。要求輸出N是Perfect、Deficient、或Abundant。 Perfect：所有因數的和 (包含1，不包含自己) 等於自己 Deficient：所有因數的和  (包含1，不包含自己) 小於自己 Abundant： 所有因數的和  (包含1，不包含自己) 大於自己 範例輸入 #1 10 5 6 16 18 21 28 29 30 40 43 範例輸出 #1 deficient perfect deficient abundant deficient perfect deficient abundant abundant deficient 解題思路 使用For迴圈判斷每一個數字的因數，如果N除以目前迴圈跑到的數字 (i) 之餘數等於0，i 就是N的因數。進行加總之後判斷是小於、等於、還是大於。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有一個包含空格字元的字串。要求輸出出現次數最多的英文字母，大小寫視為同一個字母，輸出時請輸出小寫，如果有出現次數相同的情況則由小到大輸出。 範例輸入 #1 1 Computers account for only 5% of the country's commercial electricity consumption. 範例輸出 #1 co 解題思路 先將每個字母出現的次數存放到一個Map中，接下來用Auto跑這個Map的For迴圈，並且再開一個新的Map (Key是int，Value是Vector<char>)。將舊的Map中的值乘以-1當作是新的Map的Key，並將字元Push_Back到新的Map的Value中。之後一樣用Auto跑新的Map的For迴圈，先將Vector進行排序後將裡面的字母輸出，然後就可以Break這個For迴圈因為只要輸出最多次數的字母而已。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有兩個正整數M和K，代表要將M元分給K個人。要求輸出每個人可以分到多少錢，如果有除不進的情況則將餘數分給最後一個人。 範例輸入 #1 2 1 1 4 3 範例輸出 #1 Case 1 : 第1位 : 拿1元並說DD! BAD! Case 2 : 第1位 : 拿1元並說DD! BAD! 第2位 : 拿1元並說DD! BAD! 第3位 : 拿2元並說DD! BAD! 解題思路 本題收資料的時候需要使用Long Long Int，並且K有可能會是0，當K是0時只需要輸出是第幾個Case就可以往下一個Case走了。

題目敘述 每筆測資第一行有一個正整數T，接下來會有T筆資料。每筆資料第一行有一個字串 (N = ?) 代表下面二維陣列的長寬，接下來會有N行代表二維陣列中的資料。要求輸出這個二維陣列是否為對稱矩陣。 對稱矩陣的定義為： 1. 所有元素都大於0 2. 相對於該矩陣的中心對稱 範例輸入 #1 2 N = 3 5 1 3 2 0 2 3 1 5 N = 3 5 1 3 2 0 2 0 1 5 範例輸出 #1 Test #1: Symmetric. Test #2: Non-symmetric. 解題思路 本題需使用Long Long Int來存矩陣中的資料，收資料的時候如果有收到小於0的數字，可以預設一個布林值，之後就不用進行判斷。可以將矩陣中的資料收成一維陣列，然後判斷這個一維陣列是否是迴文，這樣就可以判斷這個矩陣是否是對稱的。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行有一個包含空格字元的字串。要求由大到小輸出每一個字元出現的字數 (只需要紀錄英文字母的出現次數即可)。大小寫的字母視為同一個字元，輸出時輸出大寫的字母。如果有出現次數同樣的情況，優先輸出字母排序較為前面的字元，如A和B同樣次數，則會先輸出A再輸出B。 範例輸入 #1 3 This is a test. Count me 1 2 3 4 5. Wow!!!! Is this question easy? 範例輸出 #1 S 7 T 6 I 5 E 4 O 3 A 2 H 2 N 2 U 2 W 2 C 1 M 1 Q 1 Y 1 解題思路 先使用一個Map來存取每一個字元出現的次數，可以使用isalpha來判斷目前字元是否為英文字母，並使用toupper來將英文字母轉換成大寫的型態做Map的Key。再來使用Auto跑Map的For迴圈，並且再宣告一個新的Map (Key: int｜Value: Vector<char>)，這個新的Map是存有哪些字元出現在同一個次數上。因為題目要求要由大排到小，所以將次數乘以-1並將其字元Push_Back到新的Map中。輸出時也是用Auto跑新Map的迴圈，先將新的Map的Vector進行排序，然後再跑一個新的Map中Vector的For迴圈，將裡面的字元和目前Key乘以-1 (剛剛乘以-1現在要復原) 進行輸出。

題目敘述 本題採EOF方式收資料，每筆資料有一行含有空白字元的字串。如果有連續兩個空格的話，就將兩個空格刪減為一個空格，從左到右只要有做任何刪減就代表進行動作一次。要求輸出每個字串需要進行多少次動作。 範例輸入 #1 A very  big    joke.          Goodbye! 範例輸出 #1 2 4 解題思路 使用While迴圈來進行動作，每次跑For迴圈從左到右判斷，如果目前字元為空格且下一個字元也是空格，則將 i+1 來跳過下一個空格字元，這邊需要注意不可以超過字串長度範圍，所以判斷時要先判斷目前是否已經跑到字串的最後一個字元。輸出跑While迴圈的次數-1即可。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有一個字串，代表每個檔案的邊號。如果今天檔案編號的最後三個字元是000~009，這個檔案會被分在0號資料夾，如果是010~019，這個檔案會被分在1號資料夾，以此類推。要求輸出哪些資料夾有存放檔案和這個資料夾中有多少個檔案。 範例輸入 #1 1 000000 範例輸出 #1 0 1 範例輸入 #2 5 232944 123941 201322 234941 231320 範例輸出 #2 32 2 94 3 範例輸入 #3 5 987012 342221 223120 126641 127643 範例輸出 #3 1 1 12 1 22 1 64 2 解題思路 使用Map來存放不同資料夾的檔案數量，輸出時可以用Auto跑Map的For迴圈。

題目敘述 本題採用EOF方式收資料，每筆資料第一行有兩個正整數N和M，借下來會有M行，每行有兩個正整數a和b，代表城市a可以走到城市b，但是只能單向通過不能雙向，最後會有兩個正整數c和d。要求輸出是否能從城市c走到城市d。 範例輸入 #1 8 32 7 4 2 5 7 5 3 7 2 1 2 2 2 4 4 4 4 7 8 5 7 5 5 2 6 7 7 5 8 8 4 7 6 3 4 1 4 4 8 7 3 4 2 6 6 1 6 8 4 5 7 5 6 6 4 4 2 6 5 3 7 4 1 3 1 3 範例輸出 #1 Yes!!! 解題思路 使用Map<int, vector<int>>來存取哪些城市可以通往哪些城市，並且用BFS的方式尋找哪些城市可以通往哪些城市，如果走到終點城市就可以輸出Yes。

題目敘述 每筆測資有一個字串，字串中只會有小括弧和中括弧。要求輸出這個字串有沒有括號匹配問題。 範例輸入 #1 [([][])] 範例輸出 #1 Right 範例輸入 #2 [(]) 範例輸出 #2 Wrong 解題思路 跑字串的For迴圈，如果是左括號的話將這個字元存放到一個Vector中，如果是右括號的話判斷目前Vector最後一個字元是否跟這個右括號匹配，如果匹配的話就將Vector最後一個資料Pop_Back，如果不匹配的話直接輸出Wrong並將迴圈Break掉。如果For迴圈跑完Vector中還有資料的話也是Wrong。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有兩個正整數，分別代表預期營收值和需要的人數。最後一行有一個正整數代表總共配發幾個人，會從預期營收值最高的工廠開始配發人力，當最高 預期營收值 的工廠的人數滿足其需求之後才會開始配發次高預期營收值的工廠，以此類推。要求輸出這些人力總共配發至幾個工廠。 範例輸入 #1 3 30 10 20 5 10 3 10 範例輸出 #1 1 範例輸入 #2 4 2 6 3 2 5 7 8 9 18 範例輸出 #2 3 範例輸入 #3 6 90 5 30 6 70 8 20 4 1000 5000 500 800 5130 範例輸出 #3 2 解題思路 使用Pair將預期營收值和需要的人數存在一起，收完之後將這個Pair排序，最後面的資料就會是預期營收值最高的工廠。跑一個由大到小的For迴圈，並且每一次都將有的人數減到目前工廠所需的人數，並且建立一個存答案的變數+1。如果人數小於等於0，就Break掉For迴圈並輸出答案。

題目敘述 本題採用EOF方式收資料，每筆資料第一行有一個正整數N，代表回合數，當N等於-1時停止收資料。每筆資料第二行有一個字串是答案，第三行有一個字串代表猜測的字元。要求輸出是否有在七個猜測錯誤內猜對完整的字串。 範例輸入 #1 1 cheese chese 2 cheese abcdefg 3 cheese abcdefgij -1 範例輸出 #1 Round 1 You win. Round 2 You chickened out. Round 3 You lose. 解題思路 收到猜測字串的時候跑For迴圈判斷每一個字元，如果有猜對的話就將答案的字元Map值歸零，如果猜錯的話就把猜錯的次數+1，如果超過7次直接輸出輸了，如果在七次內猜對就輸出贏了。如果結束For迴圈之後還沒有輸出任何東西，則代表半途而廢輸出指定的字串。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行有兩個字串a和b，代表a和b兩站是連通的。最後會有兩個字串代表起點跟終點。基本價錢是10元，每搭3站要加5元，換一次線也要5元。要求輸出從起點搭車到終點最低的價格是多少。 範例輸入 #1 11 B1 B2 B2 B3 B3 B4 B4 B5 B4 G1 G1 G2 G2 G3 R1 R2 R2 R3 B2 R1 R3 G2 B1 G2 範例輸出 #1 20 範例輸入 #2 12 R1 R2 R2 R3 R3 R4 R4 R5 R5 R6 R6 R7 R7 B1 R7 Y1 Y1 B1 Y1 R1 Y1 G1 G1 R1 G1 B1 範例輸出 #2 20 解題思路 使用Map來紀錄每個車站可以到哪幾個車站，可以使用Vector的方式來存車站，因為是雙向的，所以目的地車站也要存說可以到起點車站。使用BFS的方式尋找最低金額的路線，可以使用Map將每個車站的金額存起來，如果下次有走到相同的車站就進行比較看哪一個方案的金額較低。最後輸出終點車站的Map值即可。

題目敘述 每筆測資第一行有一個正整數N，代表有N個人站成一排。第二行有一個正整數M，接下來會有M行，每行有兩個正整數a和b，代表要對a到b的人進行微鼓勵，被微鼓勵時如果目前是站著的人對坐下、坐下的人會站著，預設所有人一開始都是站著的。要求輸出在進行完所有微鼓勵後有幾個人是站著的。 範例輸入 #1 5 3 1 3 3 5 1 5 範例輸出 #1 4 解題思路 使用Map來存每一次微鼓勵的範圍，因為只要微鼓勵兩次就會變成站著等於沒有微鼓勵。將b+1之後就可以知道b-a是被微鼓勵的人數，將a和b放到Map中，如果已經有資料了就代表有重複微鼓勵的情況，所以將已經出現過的Map值做刪除，然後沒有存過的資料存到Map中。最後將Map轉換為Vector<Pair<int, int>>然後兩兩一組進行b-a的動作並將答案相加即可。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有一個字串，字串只會包含 ( )、[ ]、{ }、< > 這四種括號。要求輸出這樣的括號排序能不能配對成功。 範例輸入 #1 4 {()<>}[] (){ {(}) ()) 範例輸出 #1 Y N N N 解題思路 如果字串長度為奇數直接輸出N。可以使用Stack的概念做這題，如果跑到的字元是左括號的話就將這個字元Push_Back到一個Vector中，如果跑到一個右括號則判斷Vector中的最後一個資料是否能和這個右括號配對。如果配對成功那就使用Pop_Back將Vector最後一個資料刪除，如果配對失敗就直接輸出N然後Break掉For迴圈。另外判斷的時候也需要注意一下Vector內目前有沒有資料，如果Vector的Size是0的話代表突然有一個右括號出現，直接輸出N然後Break。For迴圈結束後也需要判斷Vector中還有沒有殘留的左括號，如果有的話同樣也是輸出N。

題目敘述 每筆測資第一行有兩個正整數代表漁船的座標，第二行有一個正整數N，接下來會有N行，每行會有兩個正整數代表一個魚群的中心座標。要求輸出距離漁船最短距離的魚群的中心座標。 範例輸入 #1 5 6 1 10 10 範例輸出 #1 10 10 範例輸入 #2 8 2 3 7 9 10 3 5 1 範例輸出 #2 10 3 範例輸入 #3 20 15 7 25 34 100 0 12 51 3 9 37 22 10 71 2 36 範例輸出 #3 3 9 解題思路 因為計算座標距離會需要用到根號，可能會有無條件捨去或進位的錯誤發生導致誤判最小值，所以可以不用在計算座標時將答案進行根號計算。

題目敘述 本題採EOF方式收資料，每筆資料第一行有一個正整數N，接下來會有N行，每行會有一個正整數，代表某一個學校的校隊有幾個人。每個學校的人都需要平均分配到不同隊，要求輸出可以最多分到幾隊。 範例輸入 #1 3 12 16 20 4 400 200 150 625 範例輸出 #1 4 25 解題思路 收資料的時候先把收到數字的因數存到一個Map中，然後建立一個Vector<Map>的資料結構將每個學校的因數Map都存放進去。之後使用Auto跑第一個學校的Map的For迴圈，並且和其他學校的Map比較看有沒有出現一樣的因數，如果所有學校都有相同的因數則先將答案設為這個因數，取最大值。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行會有一個正整數。如果這個數字非迴文，則將這個數字和這個數字反轉之後的值相加，例如195不是迴文，所以要將195加上他的反轉591，一直這個動作直到出現迴文，要求輸出需要進行多少次相加之後才會變成迴文並且該迴文是什麼。 範例輸入 #1 5 195 265 750 2 99 範例輸出 #1 4 9339 5 45254 3 6666 1 4 6 79497 解題思路 每個數字至少需要進行計算一次，所以就算一開始就是迴文了也需要計算下一次出現迴文的時間。可以將收到的資料轉換成字串或是一開始收資料的時候就收成字串型態。使用While迴圈，如果目前的數字不是迴文就一直做計算，並且每次進While迴圈計算的次數就+1。

題目敘述 每筆測資有兩個整數a和b，要求輸出b/a，無條件進位。 範例輸入 #1 25 100 範例輸出 #1 4 範例輸入 #2 3 200 範例輸出 #2 67 解題思路 判斷b%a是不是0，如果不是的話在答案上+1。

題目敘述 本題採EOF方式收資料，每筆資料有一個字串，會包含兩個數字。要求輸出這兩個數字組合而成的座標之後的位置。 範例輸入 #1 (1,5) (6,7) (10,10) (8,4) (7,9) 範例輸出 #1 ----1----- ---------- ---------- ---------- ---------- ------2--- --------5- ---4------ ---------- ---------3 範例輸入 #2 (1,1) (3,7) (2,8) 範例輸出 #2 1--------- -------3-- ------2--- ---------- ---------- ---------- ---------- ---------- ---------- ---------- 解題思路 將座標取出來之後使用Map來紀錄每一個座標的位置。之後使用For迴圈10*10，如果目前的 (i, j) 在Map中有存取資料而非0，則輸出這個Map值，如果是0則輸出-。

題目敘述 每筆測資第一行有一個正整數N，第二行會有N個正整數代表房間號碼。要求輸出每一個房間位於哪一棟大樓。 如果房號可以被 3 整除,也可以被 2 整除,此房間放置在 1 號大樓。 如果房號最後一位是奇數,但不能被 3 整除,此房間放置在 2 號大樓。 如果房號是完全平方數,或是不能被 7 整除的偶數,此房間放置在 3 號大樓。 如果上面三個條件皆不滿足，則房間在 0 號大樓。 如果同時滿足多種可能,則房間在編號最小的大樓。 範例輸入 #1 4 12 16 31 9 範例輸出 #1 1 3 2 3 範例輸入 #2 5 23 1 600 909 44 範例輸出 #2 2 2 1 0 3 解題思路 使用 if 和 else if 來判斷，這樣子如果有重複條件的編號就會直接在最前面的判斷式停下來。

題目敘述 本題採EOF方式收資料，每筆資料有一個字串。'.' 代表是空的床位，'X' 代表有人的床位，要求輸出這個字串中可以距離其他人最大的距離。 範例輸入 #1 .X.X. .X...X. .X....X. ...X 範例輸出 #1 0 1 1 2 解題思路 第一個和最後一個字元需要單獨判斷，其他的位置往左右兩邊找之後取最短的距離並且比較最大值並輸出即可。

題目敘述 本題採EOF方式收資料，每筆資料第一行有一個正整數N，接下來會有N行，每行會有一個字串。要求輸出每個字串是否有出現過，如果是新出現的字串，則輸出 "New!" 加上為第幾個新的字串，如果是已經出現過的字船，則輸出 "Old!" 加上這個字串第一次出現時所賦予的編號。 範例輸入 #1 5 eine isis zwei drei zwei 6 abc abcd abdc aabb bca abc 8 aaa aab aaa aac aaaabbbsc caa aaba aab 範例輸出 #1 New! 1 New! 2 New! 3 New! 4 Old! 3 New! 1 New! 2 New! 3 New! 4 New! 5 Old! 1 New! 1 New! 2 Old! 1 New! 3 New! 4 New! 5 New! 6 Old! 2 解題思路 使用Map來紀錄每個字串是否出現過，預設一個為1的變數來存取每個新字串的編號，如果字串為新的字串，則將這個字串的Map值設定為編號變數，然後這個變數+1。如果是舊的字串則輸出這個舊字串的Map值。

題目敘述 每筆測資第一行有一個正整數T，接下來會有T筆資料，每筆資料第一行會有一個正整數N，第二行有N個正整數代表不同長度的木棒。要求輸出每一筆資料中可以生成幾組直角三角形。 範例輸入 #1 3 3 3 4 5 6 3 3 4 4 5 5 3 3 4 6 範例輸出 #1 1 8 0 解題思路 收資料的時候同一個數字只需收一次，但是要用Map紀錄這個數字出現的次數，並且存放到陣列的時候可以先將資料進行平方。將陣列排序過後使用兩個For迴圈來取陣列中的任意兩數，代表 a^2 + b^2 = c^2 的a和b。只需判斷c是否在Map中有超過一個數量就可以判斷這樣的組合是否為直角三角形。因為同一個數字可能會超過一個，所以答案要 += MAP[a] * MAP[b] * MAP[c]。

題目敘述 每筆測資第一行有一個正整數N，接下來會有N行，每行的第一個字為一個國家名稱，剩下的字串為一個人名。要求輸出每一個國家出現的次數。 範例輸入 #1 3 Spain Donna Elvira England Jane Doe Spain Donna Anna 範例輸出 #1 England 1 Spain 2 解題思路 使用Map來紀錄每一個國家的出現次數，輸出時使用For跟Auto來將Map中的資料輸出。

題目敘述 本題採EOF方式收資料，每筆資料第一行有一個正整數N，接下來會有N行，每行有三個正整數，分別代表不同學生的語文、數學、和英文的成績。要求輸出將總分排序過後成績前5名學生的學號及總分，如果總分相同就比語文成績，如果語文成績相同學號較小的人排在前面。 範例輸入 #1 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 範例輸出 #1 6 265 4 264 3 258 2 244 1 237 8 265 2 264 6 264 1 258 5 258 解題思路 使用Vector<Pair<pair<int, int>>, int>>來存取資料並且使用Sort來排序，依序方入總分、語文、及學號，因為學號越小就會排到越前面，所以存學號的時候要將學號乘以-1，輸出的時候記得要將學號再乘以-1變回來。