# 2019 學科能力競賽南市賽題目
###### tags: `108學科能力競賽南市賽`

**鳴謝：感謝周暘典提供協助**

## Intro
本次南市賽不同以往，捨棄了筆試觀念題+上機實作題的競賽方式，而是上午3小時+下午2小時的上機實作。由於題目不會在競賽結束後公開，以下分享的皆出於記憶，儘管無法完整還原，仍有不小參考價值。
註：所有題名皆自創，部分發想於實際題名或題目內容。

競賽方式：人工 judge😅，因此並無部分給分，僅有全對/全錯，具體方式為舉手表示欲檢測的題號，出題老師會走到座位旁，要求輸入兩組測資，沒有 TLE 問題，亦不須考量記憶體的使用，若執行時間較長僅需在作答時提出等待要求。答對後，評分老師會宣讀「X號，第X題，答對」，並由工作人員紀錄題號、答對時間於白板上，並要求參賽選手核對，比賽結束後依據答對題數及答對時間排序名次（應該是先比題數，若相同才比較早答對者）。

一開始對於人工 judge 並無什麼意見，但賽後一兩天看了他人的心得，才意識到嚴重性。南市賽使用人工 judge 並不是首次了，而這樣的評分方式一直存在許多爭議，因其對於參賽者而言**並不公平**。首先這樣的判定方式並無對於記憶體使用、耗時進行限制；此外，根據筆者觀察，每題的測資大約僅有三組左右，而印有輸入測資及答案的紙張會在作答時拿到參賽者眼前（除了時間回文是直接由評審老師念出數字），其實要背下測資及答案並不難；作答時，若結果正確，評審老師會要求展示程式碼，但其目的應該只是為了防範將答案寫死並輸出，通常只是匆匆一瞥；此外，不同參賽者在作答時，輸入的測資也並非相同，要使用哪組完全由評審老師指定，我自己在作答時就遇到第一次作答使用紙上的第一、二組測資沒過，再次作答時使用第二、三組的情事，亦有可能因為測資設計的疏漏，導致 A 使用有瑕疵的寫法輸出錯誤答案，而 B 恰好避開而得分。儘管強者選手可能不受此影響，但當今日某些校內初選都已使用 Online Judge 系統時，**為何南市賽卻依舊使用如此傳統的方式？**

ref:
<iframe src="https://www.facebook.com/plugins/post.php?href=https%3A%2F%2Fwww.facebook.com%2Fbangye.wu%2Fposts%2F10157152807163241&width=500" width="500" height="475" style="border:none;overflow:hidden" scrolling="no" frameborder="0" allowTransparency="true" allow="encrypted-media"></iframe>

> [time=Fri, Nov 8, 2019 1:30 AM]
> [time=Sat, Nov 9, 2019 12:40 AM]

----
## 上午場
### 第1題：時間迴文
時間格式：`HH:MM:SS`，其中 `0 ≤ HH ≤ 23` 。
迴文範例：`00:11:00`
輸入：起始小時 終止小時
輸出：符合迴文規則的時刻 總共個數

### 第2題：你能找到嗎？
原題意為一個邊長a+b的正方形，將其重組以後變成一個邊長 b+(a+b) 和 a 的長方形，使得面積增加 1。但是定義不嚴謹（出來的形狀其實不是長方形），故以下改以數學式表達。

給定整數 N ，求符合以下二條件的兩整數 a、b。
1. a + b = N
2. a * (a + b) = (a + b) * (a + b) +1

### 第3題：Fibonacci 數
給定兩正整數 `a` 及 `b`，其中 `1 ≤ a ≤ b ≤ 1000,000,000`，問在 a 至 b 中，共有幾個 Fibonacci 數？
印象中一組大數測資：``123456789 987654321``

### 第4題：希臘占卜---生命靈數
輸入一組生日，如 196067 即表示1960年6月7日出生。
今定義
* 主命數：將生日的各位數字相加，若所得為二位數，則再次將兩位相加，直到所得為個位數。
* 天賦數：將生日的各位數字相加，取其個位數字。
* 先天數：將出生日的數字相加，若所得為兩位數，則再次相加直至所得為個位數。
* 星座數：根據不同星座，給予 1~12 中一個數字（各星座數皆爲獨特，不會重複）
註：此定義為了題目需要，與生命靈數原始定義不同。

求 1~9 的數字中，缺漏了哪幾個數字？

### 第5題：棄保效應
棄保效應：當候選人票數最低時，有一定比例的支持者會爲了避免浪費自己寶貴的一票，而轉投予次要喜歡的候選人。
原始題目中會提供各候選人發生棄保效應時，轉移的次序及比例。
給定三候選人 A,B,C，問棄保效應發生時，三位各自的票數及最終當選人。

### 第6題：後序表達式
給定一後序表達式，計算其結果（有小數）。

### 第7題：降冪多項式
輸入一多項式，輸出其降冪排列。
範例輸入：

2 5
7 100
5 0

表示 `2X^5+7X^100+5`。

範例輸出：

7X^100+2X^5+5

### 第8題：旋轉字串
輸入 N 行字串，將其旋轉 90 度後印出（包含所有合法字元，如空白、.、大小寫……）

### 第9題：全等多邊形校驗
輸入 2 組具有 N 個角的多邊形座標，求此兩個多邊形是否全等。（可翻轉、平移、旋轉）

### 第10題：走迷宮
給定一個 `N x M` 的迷宮，以「#」表示障礙物、「-」表示路，並給予起終點座標，輸出迷宮地圖，並以 S 標記起點、E 標記終點，並在行走的路徑上以 U、D、L、R 分別表示上下左右進行標記。

---
中場休息：11:30~13:30

---

## 下午場
### 第1題：五階魔方陣
求兩個 5x5 的方陣，使其符合以下條件：
1. 任一直行、橫列的和相等
2. 任一對角線和相等
3. 任一九宮格之內，與中心格子相鄰的數字和相等
### 第2題：4的組合
試用一計算式表達 1~50 中的整數，該計算式需符合下列條件：
1. 計算式中僅有 4 個 4
2. 可以使用 0.4
3. 允許的運算符號為 + - * / () √ ！

### 第3題：括號好神奇
給定一僅包含 `+` 及 `*` 的運算式，嘗試使用不同括號組合，使其結果有最大/最小值。
輸入：運算式
輸出：最大值 最小值
### 第4題：字串加密
輸入一不包含空白的字串，將其加密，規則如下：
1. 大寫字母：將其轉爲小寫，再向後位移1。 範例：X → y
2. 小寫字母：依照電話按鍵，將其轉換為對照的號碼。
3. 其餘字元：維持原狀

註：電話按鍵對照如下
* 1=1
* abc=2
* def=3
* ghi=4
* jkl=5
* mno=6
* pqrs=7
* tuv=8
* wxyz=9
* 0=0

如圖

### 第5題：最小值
給定 N 行長度不等之整數數列，求各列之最小值並輸出，最後再輸出所有列中的最小值。

範例輸入：

3 5 7 0
2 5 -1
9 10 2 3 5

範例輸出：

第1列的最小值是0
第2列的最小值是-1
第3列的最小值是2
所有列的最小值為-1

### 第6題：簡易數列操作
給定一長度未知的整數數列，最後一碼為控制碼。當控制碼為1時，輸出該數列之最小值；當控制碼為2時，輸出該數列的最大值；當控制碼為3時，輸出該數列的總和（不包括控制碼）。

範例輸入：

2 4 -1 0 9 8 2

範例輸出：

9

### 第7題：Highlight
給定一英文句子及未知列數、長度的字串，將各字串中包含句子中使用的單字保持原狀，其餘更改為「*」並輸出。

範例輸入：

This is a pencil
bxcgpnisbeqs
aqcdhjoigbnm
gjiqThisopsd
juqbdjpencil

範例輸出：

******is****
a***********
****This****
******pencil

> [time=Thu, Nov 7, 2019 12:54 AM]
> [time=Sat, Nov 9, 2019 12:45 AM]