2020 pre - HackMD

--- title: 2020 pre tags: ytp --- :::warning 作答區 * [A 組作答區](https://hackmd.io/@futurenest/2020_pre_A) * [B 組作答區](https://hackmd.io/@futurenest/2020_pre_B) * [C 組作答區](https://hackmd.io/@futurenest/2020_pre_C) * [D 組作答區](https://hackmd.io/@futurenest/2020_pre_D) ::: ## 問題 1 – 買口罩 (1_mask) ### 問題敍述為了對抗瘟疫，政府發起了購買口罩的限制，一個小朋友在7天內只能購買 5 片口罩。好奇的你想知道在連續的 𝐾 天內，自己最多能買到幾個口罩呢？能寫個程式算算看嗎？ ### 輸入格式 𝐾 輸入只有一個正整數 K，代表詢問的天數。 ### 輸出格式輸出一個整數，表示最多可購買的數量，並以換行字符結尾 ### 資料範圍 1 ≤ 𝐾 < 100 ### 資料範例 #### 輸入範例1 1 #### 輸出範例1 5 #### 輸入範例2 3 #### 輸出範例2 5 #### 輸入範例3 8 #### 輸出範例3 10 --- ## 問題 2 – 簡易數學計算機 (2_calc) ### 問題敍述小智為了教Pokémon 基本數學公式, 所以需要一個計算機程式來做數字計算練習和驗證, 由於 Pokémon 不能做太複雜的小數運算與邊界判斷, 所以這個程式不需要考慮可能有錯誤的答案、負數或非整數的情況。請你幫小智完成這支程式！ Pokémon要學習的3條數學公式(編號1 到 3)，分別表示如下: 1. `a^2+b^2=c^2` 3. `(a-b)*2=c` 4. `a * b=c` ### 輸入格式每個輸入只有一行, 並且此行有3個數字和3個逗號第一個數字p代表公式編號(1 或 2 或 3), 第二及第三個數字，依序為數學公式中的 a 或b 或c三個數字中的其中兩個。而少掉的那一個數字，可依逗號所在的位置判斷，也就是程式要計算出來的答案。 ### 輸出格式請輸出一個正整數，代表未被提供要計算出的數字 ### 資料範圍 1≤p≤3, a, b, c 必屬於正整數, 並小於10000 #### 輸入範例1 `1,3,4,` #### 輸出範例1 5 #### 範例1 說明選擇公式1. a2+b2=c2, a=3, b=4, 缺少數值c，所以c=5 #### 輸入範例2 `1,3,,5` #### 輸出範例2 4 #### 範例2 說明選擇公式1. a2+b2=c2，a=3, c=5, 缺少數值b, 所以b=4 #### 輸入範例3 `3,4,,12` #### 輸出範例3 3 #### 範例3 說明選擇公式3. a*b=c, 而a=4, c=12, 缺少數值b, 所以b=3 --- ## 問題 3 – 節奏遊戲 (3_maniagame) ### 問題敍述你有玩過音樂節奏遊戲嗎，Mania 是一種傳統的音樂遊戲類型，畫面中有 C 條軌道，隨著音樂的進行，軌道上會掉落一些物體，玩家需要在物體恰好到達螢幕的指定位置時按下按鍵，以便擊中得分。物體基本上分成兩種，第一種是單純的格子，如右方圖片中，最左邊與最右邊中間的白色格子，當它到達螢幕下方的打擊區時，就要按下鍵盤按鍵，然後放開；第二種長條，如右圖中間兩個軌道的物體，可以當作是比較長的格子，一樣要在到達螢幕下方打擊區時立刻按下按鍵，唯一不同的是要在長條完全的離開打擊區時，才放開按鍵。通常一首節奏遊戲的難度，與按下按鍵的次數有關，如果給你一個 Mania 的遊戲畫面，你能算出玩家應該要按下幾次按鍵嗎？一張譜面會是一個高度為 R，共有 C 個軌道的矩形區域，如果軌道上有一個物件，以X表示，代表該位置有一個格子需要玩家按壓，而如果一個軌道上有相鄰的X，這些X 構成一個長條。玩家也共只需要按壓一次按鍵。 ### 輸入格式 ``` 𝑅 𝐶 Row1 Row2 … RowR ``` 第一行有兩個正整數 R, C，以空白間隔，代表譜面的高度與軌道數量。接下來有 R 行，每行欄寬有 C個字元 (由空白 ’ ‘ 與大寫字母 X 構成的字串)。 ### 輸出格式輸出一個整數，表示手指需要按下去的次數，並以換行字元結尾。 ### 資料範圍 * 3 ≤ 𝑅 ≤ 1000 * 1 ≤ 𝐶 ≤ 8 #### 輸入範例1 ``` 4 1 X X X ``` #### 輸出範例1 2 #### 輸入範例2 ``` 6 4 XX X X X X XX X X X X ``` #### 輸出範例2 7 #### 輸入範例3 ``` 6 4 XX X X XX X X XX X X ``` #### 輸出範例3 12 #### 範例說明範例1，譜面高度有4行，每行欄寬1個字元，其中譜面第一行X敲擊1次，譜面第三、第四行在同一欄位上皆為X，代表這些X 構成1 個長條，玩家只需要按壓1 次按鍵。故答案為2次。範例2，譜面高度有6 行，每行欄寬4 個字元。每行的第1 個欄位皆為X，代表這些X 構成1 個長條，玩家只需要按壓1 次按鍵。其餘各欄位出現的6 個X並未構成長條，各敲擊一次。故答案為7 次。 --- ## 問題 4 – 停課人數 (4_suspension) ### 問題敍述鎮長伯伯不擅長數數，可是他想知道鎮上有多少中小學師生停課，請你幫幫他。根據教育部 2 月 20 日規定，高級中等以下學校（一）1班有1位師生被中央流行疫情指揮中心列為確定病例，該班停課。（二）1校有2位以上師生被中央流行疫情指揮中心列為確定病例，該校停課。（三）1鄉鎮市區有3分之1學校全校停課，該鄉鎮市區停課。現在給鎮上各校各班的快篩結果（11為陽性確定病例、1為陰性），請算出總停課人數。 ### 輸入格式 ``` 𝑁 𝑆1 𝐶1𝑅1𝑅2. . . 𝑅45 𝐶2𝑅1𝑅2. . . 𝑅46 …… 𝐶85𝑅1𝑅2. . . 𝑅9:5 𝑆2 𝐶1𝑅1𝑅2. . . 𝑅45 𝐶2𝑅1𝑅2. . . 𝑅96 …… 𝐶86𝑅1𝑅2. . . 𝑅9:6 …… 𝑆; 𝐶1𝑅1𝑅2. . . 𝑅45 𝐶2𝑅1𝑅2. . . 𝑅96 …… 𝐶8<𝑅1𝑅2. . . 𝑅9:< ``` 輸入的第一行包含一個正整數 𝑁，代表鎮上的學校數。接下來有 𝑁 組輸入，每組輸入的第一行包含一個正整數 𝑆=，代表第 𝑖 所學校的班級數。每組輸入接下來的 𝑆= 行，會有一個正整數 𝐶? 以及 𝐶? 個正整數 𝑅@，分別代表該所學校第 𝑗 班的人數以及該班級第 𝑘 個人的檢驗結果。 ### 輸出格式輸出一個整數於一行，代表鎮上停課人數。 ### 資料範圍 * 1 ≤ 𝑁 ≤ 10 * 2 ≤ 𝑆= ≤ 75 * 1 ≤ 𝐶? < 50 * 𝑅@ ∈ {11,1} #### 輸入範例1 ``` 3 2 1 11 1 11 2 1 1 1 1 2 1 1 1 1 ``` #### 輸出範例1 6 #### 範例説明 1 鎮上有 3 所學校，第 1所學校有2個班級，第 1所學校第1個班級有1個人，而且檢驗結果為陽性(11) 第 1所學校第2個班級有1個人，而且檢驗結果為陽性(11) 第 1所學校共有2例，故全校停課。而鎮上只有 3 所學校，1 所即達3分之1，故全鎮6人停課。 #### 輸入範例2 ``` 1 2 2 11 11 1 1 ``` #### 輸出範例2 3 #### 範例說明2 鎮上只有 1 所學校，第1 所學校有2個班級。第 1所學校第1個班級有2個人，而且檢驗結果皆為陽性(11) 第 1所學校第2個班級有1個人，而且檢驗結果為陰性(1) 校內有 2 例，雖2 例同班，仍全校3人停課。 #### 輸入範例3 ``` 2 2 3 11 1 1 1 1 2 2 11 1 1 1 ``` #### 輸出範例3 5 --- ## 問題 5 – 交換禮物 (5_gift) ### 問題敍述 Joe是一個喜歡交換禮物的校長，不只有聖誕節要交換禮物，每個月的25號都要交換禮物！然而，倘若每個月花一個下午進行抽籤、交換禮物會太浪費時間，於是Joe請Jim每個月給出全校交換禮物的小天使名單。名單中，𝑎 = 代表 𝑖 號的學生抽到的號碼，代表小天使座號。此外，Joe 發現一個班級這次交換禮物完之後會有一個分裂指數 𝐾，代表一個班級的小圈圈數量。而一個小圈圈是只從某一個人A 開始，包含他的小天使B、B 的小天使C、……、某個人的小天使Z。如：[2, 1, 4, 5, 3] 這份名單代表1號抽到2號、2號抽到1號、3抽到四號、4號抽到5號、5號抽到3號，此時這邊有兩個小圈圈 [[1, 2], [3, 4, 5]]。然而，Jim是一個常常粗心大意的人，可能在生出小天使名單時出一些差錯，如讓有些人有共同的小天使，或者有些人抽到自己，或者有些人沒有小主人等。所以想要請你幫忙寫一個程式，檢查每個班級的小天使名單。倘若名單不合法，就可以即時叫Jim修正；倘若合法，則可順便統計該班級的分裂指數。 ### 輸入格式 ``` 𝑁 𝑎1, 𝑎2 …𝑎; ``` 輸入有 2 行。第一行有一個正整數 𝑁，代表該班級的人數。第二行包含 𝑁 個介於 1 到 𝑁 之間的整數 𝑎=，代表座號為 𝑖 的同學抽到的號碼。 ### 輸出格式總共輸出一個整數於一行。倘若名單不合法，請輸出一個整數 −1；倘若名單合法，請輸出名單對應到的分裂指數 𝐾。 ### 資料範圍 * 1 ≤ 𝑁 ≤ 5 ∙ 10O * 1 ≤ 𝑎= ≤ 𝑁 #### 輸入範例1 ``` 3 2 3 1 ``` #### 輸出範例1 1 #### 範例説明 1 一號同學抽到二號、二號抽到三號、三號同學抽到一號。名單合法且只有一個小圈圈 ![](https://i.imgur.com/MAXbPMn.png) #### 輸入範例2 ``` 3 3 1 1 ``` #### 輸出範例2 -1 #### 範例說明2 二號、三號同學都抽到一號，不合法。 #### 輸入範例3 ``` 5 4 3 2 5 1 ``` #### 輸出範例3 2 #### 範例説明 3 [4, 3, 2, 5, 1] 這份名單代表1 號抽到4 號、2 號抽到3 號、3 號抽到2 號、4 號抽到5 號、5號抽到1號，此時這邊有兩個小圈圈 [[1, 4, 5], [2, 3]]。 ![](https://i.imgur.com/dHX8oFu.png) --- ## 問題 6 – Bert的報告絕技 (6_bertskill) ### 說明設想一本英語字典里的單詞，哪個在前哪個在後？顯然的做法是先按照第一個字母、以 a、b、c……z 的順序排列；如果第一個字母一樣，那麼比較第二個、第三個乃至後面的字母。如果比到最後兩個單詞不一樣長（比如，sigh 和 sight），那麼把短者排在前。字典序的大小通俗來說，字典序大即指在以字典序排列時排在後面，反之亦然。例如， bike 排在 bag 的後面，那麼 bike 就比 bag 的字典序要大。 ### 問題敍述那個男人Bert，傳說只要有報告的課程他都可以輕鬆A+。現在你選到了大學國文一，為了避免得到C，於是你決定向Bert求助。但Bert可不會輕易告訴你他的獨家絕技，於是Bert給你了一個 𝑛 × 𝑚 的表格，為了知道Bert的絕技，你需要從表格中找出一條從表格左角走到右下角的路徑其走過的格子所組成的字串字典序最小。不過Bert也不想刁難你，因此走的路徑只能向右或向下，若你能找到那樣的字串並告訴Bert，也許他就會告訴你他的絕技呦~ 如果字串𝑠字典序比字串𝑡小，則代表能夠找到一個最小的非負整數𝑖 (0 ≤ 𝑖 ≤ 𝑠的字串長度)使得 𝑠= ≠ 𝑡= 且 𝑠= < 𝑡=。 ### 輸入格式輸入的第一行包含兩個正整數 𝑛,𝑚，分別代表表格的行數與列數。接下來𝑛行，每行有𝑚個字元，且皆為小寫英文字母。 ### 輸出格式請輸出一行，代表從表格左上角(1, 1)走到右下角(𝑛,𝑚)的路徑中所組成字串中字典序最小的字串。 ### 資料範圍 * 1 ≤ 𝑛 ≤ 15 * 1 ≤ 𝑚 ≤ 15 * 保證給定的字元皆為小寫英文字母。 #### 輸入範例1 ``` 2 4 winn fssf ``` #### 輸出範例1 wfssf #### 範例説明 1 組成最小字典序的路徑為(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4)。 #### 輸入範例2 ``` 3 3 nas mwt rxt ``` #### 輸出範例2 nastt #### 範例說明2 組成最小字典序的路徑為(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)。 #### 輸入範例3 ``` 2 3 yac qdw ``` #### 輸出範例3 yacw #### 範例説明 3 組成最小字典序的路徑為(1, 1) -> (1, 2) -> (1, 3) -> (2, 3)。 --- ## 問題 7 – 大陣列 (7_bigarray) ### 問題敍述現在你有一個 𝑁 × 𝑁 的大二維陣列 𝑎[𝑁][𝑁]（陣列的編號從 0 開始），一開始陣列中所有的位置的數值都是 0。接下來，你會有 𝑀 次的操作，第 𝑖 次操作的內容是把陣列中的 𝑎[𝑥=][𝑦=] 的值修改為 1。題目保證所有的 (𝑥=, 𝑦=) 都相異。做了 𝑀 次操作後，請你算出有多少的 (𝑐, 𝑑, 𝑒, 𝑓)，滿足以下的條件： ![](https://i.imgur.com/KZZ7baV.png) ### 輸入格式 ``` 𝑁 𝑀 𝑥1 𝑦1 𝑥2 𝑦2 …… 𝑥f 𝑦f ``` 輸入的第一行包含兩個正整數 𝑁,𝑀，分別代表陣列的大小，以及操作的數量。接下來的 𝑀 行，每行包含兩個整數 𝑥=, 𝑦=，代表第 𝑖 次操作要修改的位置。 ### 輸出格式輸出一個整數於一行，代表符合題目敘述條件的 (𝑐, 𝑑, 𝑒, 𝑓) 的數量。 ### 資料範圍 * 1 ≤ 𝑁 ≤ 100000 * 0 ≤ 𝑀 ≤ 100000 * 0 ≤ 𝑥=, 𝑦= < 𝑁 * 保證所有的 (𝑥=, 𝑦=) 都相異 #### 輸入範例1 ``` 3 1 1 1 ``` #### 輸出範例1 4 #### 範例説明 1 修改完後，題目的陣列為： 000 010 000 符合題目條件的 (𝑐, 𝑑, 𝑒, 𝑓) 為 (0, 0, 1, 1), (0, 1, 1, 2), (1, 0, 2, 1), (1, 1, 2, 2)。 #### 輸入範例2 ``` 4 0 ``` #### 輸出範例2 0 #### 範例說明2 沒有符合題目條件的 (𝑐, 𝑑, 𝑒, 𝑓)。 #### 輸入範例3 ``` 8 8 0 0 0 1 3 6 7 7 6 2 4 2 6 4 5 1 ``` #### 輸出範例3 104