---
tags: Academic
---
# 題解：紫荊組
[Final Scoreboard](https://i.imgur.com/fnMpyVz.jpg)
## 說明
by 黃鈺程、曾俊宏
有鑒於不少隊伍於比賽過程對於比賽模式進行提問，在此補充說明一下程式競賽是怎麼進行的。
1. 隊伍將程式碼 submit 後，裁判這邊**並不是**手動輸入幾筆測資看程式碼有沒有正確輸出。裁判這邊是透過程式，將預先產生的好的測資餵進你的程式，我們一般情況下不會去手動跑你的程式。所以程式碼中並不用寫 `printf("請輸出測資")` 之類的東西，這反而會造成你的程式碼被判定為 Wrong Answer。
2. 測資餵進你的程式時，表現得像是有人在手動輸入一樣，所以你只須從標準輸入讀資料（即使用 `scanf` 或 `cin`），並不需要自行開檔，然後從檔案讀入。
3. 餵進你的程式的測資通常會跟題目中給的範例輸入不同（但當然會符合題目中的技術規格與輸入格式），測資中也通常會包含非常強的測資，即數字會是技術規格中所說的上限）
4. 當讀進資料後，你的程式應該符合輸出格式地輸出答案然後停止。一般來說每筆測資輸出一行，最後一筆測資後也是如同其他測資要換行。
5. 答案不用等到全部讀完才一起輸出，也就是說你在輸入很多比測資的時候，算好就可以輸出答案了!
6. 如果你的程式能在題目所說的時限內輸出答案，那裁判這邊的程式會比對你的輸出與正確答案，來確定你是 Correct 還是 Wrong Answer 或其他。
7. 其他常見的結果為：Time Limit Exceeded（你的程式跑到題目規定的時間到了還沒終止）、Runtime Error（你的程式跑一跑 crash 了，通常是程式碼中有 bug）、Presentation Error（你的程式輸出多餘的東西，不符合題目的輸出格式）、Compilation Error（你傳上來的程式碼根本無法編譯…請先在你的電腦編一下，確定可以再傳上來）。
以這次比賽來說，除了第一題與第五題以外，其他題都可以使用以下程式碼架構：
C:
```c=
#include <stdio.h>
int main() {
int testcase;
scanf("%d", &testcases);
while (testcases--) { // 總共會跑 testcases 次
// 讀入測資
// 運算
printf("%d\n", ans); // 輸出答案，記得換行
}
return 0; // 記得加，不加有時會被造成問題
}
```
C++:
```cpp=
#include <iostream>
using namespace std;
int main() {
int testcases;
cin >> testcases;
while (testcases--) { // 總共會跑 testcases 次
// 讀入測資
// 運算
cout << ans << endl; // 輸出答案，記得換行
}
return 0;
}
```
Python 中 `input()` 是整行輸入，而 `print` 預設會自動加上換行：
```python=
def solve():
# 讀入測資
# 運算
print(ans)
TC = int(input())
for _ in range(TC): # 執行 TC 次
solve()
```
另外，在使用 C++ 讀入時要小心，`cin` 會根據你變數的型態來決定他要怎麼讀，如果假設輸入是：
```
123.456
```
是浮點數，如果你使用
```cpp
int a;
cin >> a; // a = 123
```
那 `a` 會是 `123` 而不是你預期的 `123.456`。正確的寫法是：
```cpp
float a;
cin >> a; // a = 123.456
```
## 道歉啟示
對於 房地產投資客 和 K進制轉換 兩題的題目中出現的錯誤，我們均是在比賽進行中和題解撰寫時才發現。對於這些錯誤，我們會銘記在心，並會在下一屆比賽時特別注意。
## A. 多少錢
題目：教授
題解：黃鈺程
讀入 4 個正整數，輸出結果。
[C++ by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%A4%9A%E5%B0%91%E9%8C%A2/henry.cpp)
## B. 金錢規劃
題目：教授
題解：曾俊宏
照著題目做即可!
先讀取總測資數後，對於每一筆測資讀兩數字整數(分別是收入 $I$ 與支出筆數 $N$)，之後再讀取 $N$ 個數字並且從 $I$ 中扣除即可!
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%87%91%E9%8C%A2%E8%A6%8F%E5%8A%83/amos.py)
[C++ by 郭晏誌](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%87%91%E9%8C%A2%E8%A6%8F%E5%8A%83/macaca.cpp)
## C. 清償卡債
題目：教授
題解：黃鈺程
照著題目做~記得使用 `float` 或 `double` 來存有小數點的變數。在計算 30 次方時，你可以自己寫個迴圈，也可以使用 C/C++ 在 `math.h`/`cmath` 下內建的 `pow`。
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%B8%85%E5%84%9F%E5%8D%A1%E5%82%B5/amos.py)
[C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%B8%85%E5%84%9F%E5%8D%A1%E5%82%B5/andy.cpp)
[C++ by 陳煒杰, pow](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%B8%85%E5%84%9F%E5%8D%A1%E5%82%B5/andyforpow.cpp)
## D. 房地產投資客
題目：教授
題解：黃鈺程
非常抱歉，這題題目有一點小瑕疪，我們現在寫題解時才注意到：題目關於「投入金額、房貸利率、操作次數」的型態，輸入格式、技術規格、範測是不太一致的。我們測試的測資裡使用的是技術規格中所說的 float, float, int。這可能造成部份隊伍只使用範測測試是找不出這種情況的。
另外這題在 judge 時有開放浮點數誤差，只要你的結果與答案誤差在 0.1 以下即可。比賽中會 rejudge（沒有影響到紫荊組） 來自於 pc^2 會錯誤估計程式執行時間，他把他判斷是否在誤差內的時間也算進去，而他判斷的時間莫名的長……。至於有些隊得到的 Incomplete Output，是因為在 pc^2 的誤差處理機制有瑕疵。如果最後一筆測資在輸出答案的時候並沒有輸出換行，會造成比對錯誤。
另外比賽中有許多隊沒看到要輸出結果至**小數點後二位**，造成無法 AC。
Python(3.6) 的寫法是 `print(f'{ans:.2f})'`
C 的寫法是 `printf(“%.2f“, ans);`
C++ 的寫法是 `cout << fixed << setprecision(2) << ans << endl;`
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%88%BF%E5%9C%B0%E7%94%A2%E6%8A%95%E8%B3%87%E5%AE%A2/amos.py)
[C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E6%88%BF%E5%9C%B0%E7%94%A2%E6%8A%95%E8%B3%87%E5%AE%A2/andy.cpp)
## E. 工讀金
題目：教授
題解：黃鈺程
這題是考你 IO。這種不知道要讀多少，只知道讀到什麼才結束的情況，可以使用無窮迴圈來讀（我知道許多老師不建議使用，不過總是難免的，當然你可以引入一些指示用的變數來讓可讀性增加），你可以這樣寫成：
```cpp
while (true) {
int x; cin >> x; // or scanf(" %d", &x)
if (x == 0) {
break;
}
}
```
如果你迴圈中的第一行一定是讀入變數，那你可以寫成
```cpp
int x;
while (cin >> x && x != 0) { // or while (scanf(" %d", &x) && x != 0)
// ...
}
```
於是這題就輕鬆解決啦~
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%B7%A5%E8%AE%80%E9%87%91/amos.py)
[C++ by 郭晏誌](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%B7%A5%E8%AE%80%E9%87%91/macaca.cpp)
[C++ by 陳煒杰](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%B7%A5%E8%AE%80%E9%87%91/andy.cpp)
## F. 計算矩形數量
題目：教授
題解：郭晏誌、黃鈺程
這題因為 N 很小，所以我們可以用暴力的方法解：枚舉所有可能的矩形位置。我們用 2 個 for 枚舉矩形的左上角位置，2 個 for 枚舉矩形的右下角位置，之後我們檢查這個矩形的四個角是不是都是 1。整體時間是 $O(N^4)$。
數學一點的解法就是矩陣列運算如果是矩形的話對應位置的 1 會被扣成 0， 所以矩陣的列相減之後 seqential 檢查是否有原本是 1 的位置相減之後變成 0。
以第一行往下對第二第三行做列運算:
1.第二行的第一個 1 與最後一個 1 被扣成 0，這就告訴我們它可以湊出一個矩形。
2.第三行的第三個 1 與最後一個 1 被扣成 0，這就告訴我們它可以湊出一個矩形。
1 0 1 0 0 1 1 0 1 0 0 1
1 0 0 0 0 1 -> 0 0 -1 0 0 0
0 0 1 0 0 1 -1 0 0 0 0 0
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%A8%88%E7%AE%97%E7%9F%A9%E5%BD%A2%E6%95%B8%E9%87%8F/amos.py)
[C++ by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E8%A8%88%E7%AE%97%E7%9F%A9%E5%BD%A2%E6%95%B8%E9%87%8F/henry.cpp)
## G. K 進制數字
題目：教授
題解：曾俊宏
再次抱歉，這題題目我們 review 時沒有發現 51 被打成 52。
這題最核心的最法是使用長除法! 以十進位的 51 換成三進位表示法的話，過程如下:
1. 51 / 3 商 17 餘 0
2. 17 / 3 商 5 餘 2
3. 5 / 3 商 1 餘 2
4. 1 / 3 商 0 餘 1
所以，我們可以得到 $(51)_{10}$ 換底之後的答案就是 $(1220)_2$ 啦!
但是這一題有兩個坑，要看你怎麼實作，才知道會不會遇到。
### 坑一
$N = 0$，如果你是類似這樣寫
```
int ans[100];
int i = 0
while(N > 0)
{
ans[i] = N % k;
N /= K;
i++;
}
```
想想看 0 的 case 你的 output 會是什麼?
### 坑二
如果你把答案記錄在int裡面，我們看看下面這一組測資: 十進位 $9123$ 換成二進位會是 $10001110100011$，這個答案會不會超過 c/c++/java的 int 可以存的範圍呢? 會喔~
[C++ by 李晨維](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%80%B2%E5%88%B6%E8%BD%89%E6%8F%9B/tom.cpp)
[C++ by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%80%B2%E5%88%B6%E8%BD%89%E6%8F%9B/henry.cpp)
## H. 單字背誦
題目：黃鈺程、郭晏誌
題解：黃鈺程
這題是經典的一筆畫問題。用圖論的語言來講，是尤拉環（Euler Circuit）。每筆測資可以轉換成一個有向圖 $G$。每個單字是圖中的邊，圖的節點是字母，例如 `[electricity, yarn, negotiate, abandon, ninja]` 與 `[xy, yx, ab, ba]` 分別建成圖：
題目所求就是在問 $G$ 是不是一個或多個歐拉環所組成，而這可以藉由檢查圖中是不是每個節點的入邊數（in degree）等於出邊數（out degree）。這個 **充要關係** 可在各離散課本找到，因此不在此說明。題外話，如果這題改成問給定的單字可不可以組成 **僅一個** 歐拉環，那就得先判這個圖中所有 degree ≠ 0 的點是連通的喔。
不過如果不知道尤拉環，這題也是某種程度可以解出來的：
1. 每個單字只有字首與字尾的字母有意義，中間有什麼字母不影響結果。
2. 如果一筆測資是 Lucky，則對於任意字母，它「出現在單字字首的次數」要等於「出現在單字字尾的字數」。
這可以用反證法證明：假設這些單字是 Lucky，且字母 c 出現在字尾的次數比出在字首的次數多一，則會有一個字尾為 c 的單字找不到下一個單子繼續接，因此不是 Lucky。
至此，你就可以 **猜說** 是不是統計一下各字母的情況，來判定是 Lucky 還是 QAQ。這剛好會是對的，不過不正確，因為並沒有在邏輯中證明這是「若且唯若」的關係。上述只證明了 => 的關係，並沒有 <=，也就是說如果統計的結果成立，那這筆測資就一定是 Lucky 嗎？（答：是的，性質由歐拉環的證明保證）。
我不知道解出這題的選手們是不是都有注意到這個，不過就算沒有，既然是比賽，證明不嚴謹是可以接受的啦~有想法比較重要。這題被許多應該沒聽過歐拉環的人（非資工系的選手與資工大一）解出來，讓我非常驚訝！
這題實作非常簡單，統計一下即可，利用英文字母的 ASCII Code 是連續的，可以直接開陣列算一下各字母的次數。
[Python by 黃鈺程](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%96%AE%E5%AD%97%E8%83%8C%E8%AA%A6/solution.py)
[C++ by 郭晏誌](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E5%96%AE%E5%AD%97%E8%83%8C%E8%AA%A6/macaca.cpp)
## I. 選課
題目：曾俊宏、黃鈺程、陳煒杰
題解：曾俊宏
這題其實在冗長的題目敘述背後，只是要求取不超過 $K$ 的重疊總長下，的最大的區間覆蓋長度值。
由於這一題的 $N$ 只有 $18$，所以我們可以對於所有的可能區間組合進行枚舉，並對於每次的枚舉組合進行重疊總長度的計算。只要重疊總長度不高過 $K$， 我們就嘗試更新最大值。
實作部分，可以使用二進制數字的性質進行爆搜，也可以使用 DFS 來進行爆搜。
[C++ 二進制爆搜 by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%81%B8%E8%AA%B2/solution.cpp)
[C++ DFS爆搜 by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%81%B8%E8%AA%B2/solution2.cpp)
[Java 二進制爆搜 by 曾俊宏](https://github.com/henrybear327/2018-CCU-Pineapple-Contest/blob/master/%E9%81%B8%E8%AA%B2/Main.java)
Sign in with Wallet
Connect another wallet