# TOI 2020/12 新手同好會程式解析
## [第一題] [紅綠燈](https://toi-reg.csie.ntnu.edu.tw/question/202012-onsite/TrafficLight.pdf)
---
### 解題思路
先直觀思考前幾種狀況，用已知變數，列出他們對應的不等式。
根據題目敘述，以下設紅燈秒數為`r`，綠燈秒數為`g`，小明走路秒數為`s`
開始之前先提醒自己：不等號要特別小心。
題目假設***只要小明抵達路口時還是綠燈，他就一定可以（飛奔）通過路口***，數學上的意義是，只要是綠燈就算可以通過。
$g$ 秒那一瞬間，燈號由綠轉紅，不算是綠燈。$(g+r)+g$ 秒同理。
$g+r$ 秒那一瞬間，燈號由紅轉綠，算是綠燈。$(g+r)+(g+r)$ 秒同理。
:::spoiler <法一> 先判斷碰到綠燈的狀況
| Case | 說明 | 不等式 |
| -------- | -------- | -------- |
| 1 | 第一次紅燈結束前 (s未滿g秒) | $s<g$ |
| 2 | 第一次紅燈結束後、第二次綠燈結束前 | $(g+r) \le s < (g+r)+g$ |
| 3 | 第二次紅燈結束後、第三次綠燈結束前 | $(g+r)+(g+r) \le s < (g+r)+(g+r)+g$ |
因為在判斷碰到綠燈的可能，所以**只要是綠燈，都要記得加等號**。
接著，請問Case n-1的不等式長什麼樣子呢？沒錯，就是
$(g+r)\times n \le s < (g+r)\times n+g$
這個一般式概括了所有情況。
Case 1把它改成$0\le s< g$，方便接下來的推導。
輸入`s`不會真的是0秒，不用擔心輸入$0$會出問題。
觀察所有Case共同的規律，如何化成此題的判斷條件，無論n是多少都適用？
我們把一般式同取除以$(g+r)$的餘數：
$0 \le s\mod (g+r) < g$
在程式實作時，兩個不等式拆開，再用and符號連接，此即判斷條件。
#### 程式碼1
```cpp=
#include <iostream>
using namespace std;
int main(){
int r, g, s;
cin >> r >> g >> s;
if (s % (r+g) >= 0 && s % (r+g) < g)
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}
```
由於r, g, s均為正數，`s % (r+g)`的結果必大於等於0，因此前面那個條件，根本可以不用。上面的程式可以簡化為：
#### 程式碼2
```cpp=
#include <iostream>
using namespace std;
int main(){
int r, g, s;
cin >> r >> g >> s;
if (s % (r+g) < g)
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}
```
:::
:::spoiler <法二> 先判斷碰到紅燈的狀況
| Case | 說明 | 不等式 |
| -------- | -------- | -------- |
| 1 | 第一次綠燈結束後、第一次紅燈結束前 | $g \le s < g+r$ |
| 2 | 第二次綠燈結束後、第二次綠燈結束前 | $(g+r)+g \le s < (g+r)+(g+r)+g$ |
| ... | ... | ... |
| n | 第n次綠燈結束後、第n次綠燈結束前 | $(g+r)\times (n-1)+g \le s < (g+r)\times n$ |
同樣為了概括不同的n，我們把不等式同除以$(g+r)$取餘數。
這次不能直接轉換，$g \le s\mod (g+r) < 0$ 不是個合理的不等式。
我們拆開來想想看。左邊不等式是：
$g \le s\mod (g+r)$
很正常，沒什麼問題。
右邊的話，因為$s$ 差點被(綠+紅)整除，那餘數一定非常大，最大是$g+r-1$
所以應該改成：
$s\mod (g+r)\le g+r-1$
但這個式子其實沒有必要。餘數運算有上限是必然的結果，這一題規範下限，意即使用左邊這個不等式即可。程式如下：
#### 程式碼3
```cpp=
#include <iostream>
using namespace std;
int main(){
int r, g, s;
cin >> r >> g >> s;
if (s % (r+g) >= g)
cout << "no" << endl;
else
cout << "yes" << endl;
return 0;
}
```
程式碼3跟程式碼2比起來，只是換了不等號，yes/no換位置，執行結果一致。
:::
## [第二題] [歌唱大賽](https://toi-reg.csie.ntnu.edu.tw/question/202012-onsite/Singer.pdf)
---
### 解題思路
* 為了儲存評審人數，需要有一個變數`n`。
* 為了儲存每位評審的給分，需要根據`n`值，宣告**陣列**`a[n]`
* 使用迴圈結構（**for-loop**），一一定義陣列元素，儲存給分
* 使用迴圈結構，一一尋找**最大值**、**最小值**和總和
* 將總和扣掉最大值和最小值，即為所求
---
### 如何尋找最大值/最小值
:::spoiler [子題一] 三數找極值
如果不會從多數找極值，就先從這題下手吧！
這個解法不能類推到第二個子題，但思考的過程，對於未來學習**排序演算法**是有幫助的。
三數找極值，需要用巢狀選擇結構（if-else）與不等式來比大小。
開始之前先想想，最多需要比幾次呢？
* **Step 1. 用數學關係找出所有可能性**
三個數比大小，總共有幾種可能？這是個排列組合問題。
由小排到大或由大排到小，共有$3\times 2\times 1 = 6$ 種可能。
確認可能性的數量，當程式出現錯誤，你才找得出到底少了哪一種組合。
* **Step 2.用樹狀結構條列判斷步驟**
三個變數加上大於小於符號，馬上開始寫if-else，一定會亂成一團。
稍安勿躁，先在紙上或腦中，寫出你的判斷順序。
畫完圖之後會發現，最少2次、最多3次比較，才能確定abc的大小關係。
```graphviz
digraph hierarchy {
nodesep=1.0 // increases the separation between nodes
node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
edge [color=Blue, style=dashed, fontcolor=darkgreen] //All the lines look like this
"a<b?"->"b<c?" [label="a<b"]
"a<b?"->"a<c?" [label="a>=b"]
"b<c?"->"a<b<c" [label="b<c"]
"b<c?"->"c<a?" [label="b>=c"]
"c<a?"->"c<a<b"[label="c<a"]
"c<a?"->"a<=c<b"[label="c>=a"]
"a<c?"->"b<=a<c"[label="a<c"]
"a<c?"->"c<b?"[label="a>=c"]
"c<b?"->"c<b<=a"[label="c<b"]
"c<b?"->"a<=b<=c"[label="c>=b"]
}
```
* **Step 3.用if-else實作**（程式碼略）
實作為3層if-else巢狀迴圈。有些同學可能想，咦我可以用邏輯運算子呀！
像是`a<b && b<c`，那六種情況在同一層就解決了。這樣當然可以，但很容易出錯。上面的樹狀結構，最下面的節點確實有6種，但有的有等號有的沒有，很容易出錯，漏掉同分的情況，須要特別小心。
:::
:::spoiler [子題二] 多數找極值
多數找極值，顯然不能用前面的方法了。我們根本不知道有幾個數，就算知道了，各種可能也會比得沒完沒了。回到最初的問題，目的是找出最大值和最小值，其實根本沒有必要找出每一個數之間的大小關係。
開始之前，先假設一個情境：你眼前有一堆分數沒排序的考卷，你該如何尋找最高分的那一張呢？沒意外的話，你不可能記下所有數字，而是一個、一個數字仔細尋找，腦中只記一個數字：最高的那一個。
程式也是這樣的。運用迴圈結構，一個、一個數字去檢查，用一個變數`max`，記載目前為止的**最大值**。當考卷翻閱完畢，最高分就出來了。尋找最低分的考卷，也是一樣的道理。
至於最大值、最小值的初始值是多少呢？有兩種不同的想法：
1. 把兩個都設成第一眼看到的數字。
1. 分別設為確定比所有數字都小/大的數字。以考卷這題為例，滿分100分的話，就分別設成`-1`和`101`。
:::
---
### 程式碼
依照解題邏輯一步一步做的話，程式碼長這個樣子：
:::spoiler 程式碼1
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
for(int i=0; i<n; i++){
cin >> a[i];
}
int min = a[0], max = a[0], sum = 0;
for(int i=1; i<n; i++){
if (a[i] < min) min = a[i];
if (a[i] > max) max = a[i];
sum += a[i];
}
cout << sum - min - max << endl;
return 0;
}
```
:::
<br />
仔細看會發現，上面跟下面的for-loop，都是重複n。
把數字一個一個輸入，跟找總和、最大值、最小值，其實可以在同一個迴圈。
:::spoiler 程式碼2
```cpp=
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
int min = a[0], max = a[0], sum = 0;
for(int i=0; i<n; i++){
cin >> a[i];
if (a[i] < min) min = a[i];
if (a[i] > max) max = a[i];
sum += a[i];
}
cout << sum - min - max << endl;
return 0;
}
```
:::
<br />
最後，有沒有人在想，就沒有辦法不能把所有數字排序一遍嗎？當然有，但排序法的程式比較難寫，今天先用懶人法：內建函數。
c++有一個函式庫`algorithm`，裡面有個函數`sort()`，可以將陣列由小排到大，有興趣的可以自己google看看。這題如果使用sort的話長這樣：
:::spoiler 程式碼3
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
int sum = 0;
for(int i=0; i<n; i++){
cin >> a[i];
sum += a[i];
}
sort(a, a+n);
cout << sum - a[0] - a[n-1] << endl;
return 0;
}
```
:::
## [第三題] [傳送門](https://toi-reg.csie.ntnu.edu.tw/question/202012-onsite/Portal.pdf)
:::spoiler 程式碼1
```cpp=
#include <iostream>
using namespace std;
int main() {
int a, b, n;
cin >> a >> b >> n;
int door[n];
for(int i = 0; i < n; i++){
cin >> door[i];
}
// find idx of a and b
int ia, ib;
for(int i = 0; i < n; i++){
if(door[i] == a) ia = i;
if(door[i] == b) ib = i;
}
// swap idx of a and idx of b to ensure ia < ib
int temp;
if(ia>ib){
temp = ia;
ia = ib;
ib = temp;
}
// sum up
int sum = 0;
for(int i = 0; i < n; i++){
if(i == ia) i = ib+1;
sum += door[i];
}
cout << sum << "\n";
return 0;
}
```
:::
:::spoiler
:::
Sign in with Wallet
Connect another wallet