110資訊學科能力南區賽題目

# 110資訊學科能力南區賽題目 111資訊學科能力南區賽題目在 https://hackmd.io/@victor26/Bk_WgWGri 備註：需要通靈出來的完整版題目在 sorce code 裡，想體會南區賽原汁原味的可以先把它關掉owo ## 上午場 ### p1 給你 $N$ 個人的成績( $N\leq30$ )，保證所有成績都介於 $0\sim100$ )。第一行把大家的成績由小到大輸出。第二行輸出不及格的最大分數，如果所有人都及格輸出 `best case`。第三行輸出及格的最小分數，如果所有人都不及格輸出 `worst case`。 ### p2 輸入字串 $S$，判斷是否為回文。 ### p3 多筆輸入，每筆有兩行，第一行輸入一個陣列，第二行輸入兩個正整數 $N,\,M$ 。如果 $N=1$ ，把最後一個元素 pop 出來，並且 push back $M$ 。如果 $N=2$ ，把第一個元素 pop 出來，並且 push back $M$ 。如果 $N=3$ ，從最後一筆資料開始把 $M$ 後的所有數都 pop 掉。如果 $N=4$ ，從最後一筆資料開始把 $M$ 前的所有數都 pop 掉。最後輸出陣列的值，如果陣列是空的輸出 `NF` 。 ### p4 給定 $N$ 個長度為 $a_i$ 的柱子，相鄰間隔為 $1$。挑選 $i<j$ 使 $\min(a_i,a_j) \times (j-i)$ 最大。 ### p5 輸入一正整數 $N$，代表正方形衛生紙一邊上有 $N$ 個方格。每個方格可以塗成黑色或白色，例如 $N=2$ 有 $5$ 種可能： ``` [B]lack/[W]hite BB BW WB WW WW BB WW WW BW WB ``` 問有多少種可能。範例輸入 ``` 2 1 8 ``` 範例輸出 ``` 5 1 204 ``` ### p6 給一個網格圖，每個格子上有一個權值，權值介於 $[0,\,N^2-1]$ 且互不重複，並且給定終點，從 $(0,0)$ 開始走，每次往上下左右中沒被走過並且權值最小的格子走，問走到終點要花幾步，或者判斷沒辦法走到終點。 ### p7 輸入一正整數 $N$。輸出 $B$、$C$，分別代表 $N$ 在二進位下的表示，以及二進位下包含多少個 $1$。 ### p8 給你一個長度為 $N$ 的陣列，當中只有 $10,\,20,\,50,\,100,\,200,\,500,\,1000$ 這七種可能的值，現在你每次操作可以把任意一個元素放到任意一個位置，要使得所有同樣值的元素都在一個連續的區間內，問最小操作次數。 $N \leq 105$ ### p9 高速公路上有 $N$ 個廣告看板，現在要讓每 $M$ 個連續的廣告看板都有被投放至少 $K$ 個廣告，在最小投放數量下，有幾種可能的投放方法？ $1 \leq K \leq M \leq 50,\,M \leq N \leq 10^9$。 ### p10 給你兩篇文章 $A,\,B$，文章中有數個段落，每個段落都有數個行，每行都由數個字元組成，問你 $B$ 文章出現在 $A$ 文章的哪個段落、哪行的哪個字元到哪個段落、哪行的哪個字元。每篇文章段落數 $\leq 20$，每個段落總字元數 $\leq 300$。 ## 下午場 ### p1 有一隻蝙蝠飛行速度 $v$，距離牆壁 $d$ 公尺，現在溫度 $t$，音速在空氣中速度為 $321+0.6t$，求蝙蝠收到回音時距離牆壁的距離(四捨五入到小數第二位) ### p2 輸入正整數 $N$，代表長度為 $N$ 的序列，所有元素皆為 $0$。每次把第 $ax + b$ （$x$ 是所有的非負整數）個都加 1 問最後結果。 ### p3 輸出所有 $a \sim b$ 整除 $4$ 或 $9$ 的所有數，並輸出總數跟總和輸出格式：一行十個數字，欄寬四格（長度為四向左對齊，不足補空白）範例輸入： ``` 4 9 ``` 範例輸出： ``` 4 8 9 3 21 ``` ### p4 給 $n$ 段線段 $[l_i,\,r_i]$，求覆蓋的聯集長度 ### p5 求樹直徑長度。 ### p6 輸入一字串 $S$，輸出其是否為合法密碼。該密碼符合以下條件為合法： 1. 長度必須 > $8$ 2. 必須包含英文字母和數字 3. 至少包含一個大寫英文字