---
# System prepended metadata

title: 110資訊學科能力南區賽題目
tags: [Problems]

---

# 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. 至少包含一個大寫英文字