---
tags: 109_FDCS
---
# 插班考試卷
<!-- 初階班難度 -->
# 第一大題
## p1. 又來爬樓梯
### 題目敘述
小民要爬一個有n階的樓梯，一次可以上 1,2,3階，請問他一共有幾種上樓梯的方法。
### 輸入說明
多筆輸入
輸入一個正整數n(1≤n≤30)代表樓梯的階數
### 輸出說明
輸出一共有幾種走法，保證答案在int 裡面
### 範例輸入
```=
1
2
3
```
### 範例輸出
```=
1
2
4
```
### 試題內容
```cpp=
#include <iostream>
using namespace std;
int main() {
int a[32];
a[0] = 1; a[1] = 2; a[2] = 4;
for (int i = 3; i <= 30; i++) {
(...A...) // 建構到各階樓梯走法
}
int n;
while (cin >> n) {
cout << (...B...) << endl; // 輸出題目要求
}
}
```
## p2. 努力100分
### 題目敘述
大家一定都聽過以下這段話:
如果將字母A到Z分別編上1到26的分數(A=1,B=2...,Z=26)
你的知識(KNOWLEDGE)得到96分(11+14+15+23+12+5+4+7+5=96)
你的努力(HARDWORK)也只得到98分(8+1+18+4+23+15+18+11=98)
你的態度(ATTITUDE)才是左右你生命的全部(1+20+20+9+20+21+4+5=100)
好的 那麼現在有一些字母 會有大寫的字母 當然也有小寫的 你要做的是把字母化為數字再加起來
### 輸入說明
多筆輸入
輸入一串字母和一些雜七雜八的東西 當輸入0的時候結束程式
### 輸出說明
輸出數字加總 而且大小寫不影響 請詳見範例輸出
> 但如果輸入內容出現英文字母以外的東西 請輸出 "多元選修好難喔" (不含引號)
> 如果數字加總為100 輸出 "Perfect!"(不含引號)
> 如果超過100 輸出"U should take a break"(不含引號)
### 範例輸入
```=
hardwork
HaRdwoRK
aTtitUde
123456asd
aTtitUte
0
```
### 範例輸出
```=
98
98
Perfect!
多元選修好難喔
U should take a break
```
### 試題內容
```cpp=
#include <iostream>
#include <cctype>
using namespace std;
int main () {
string s;
while (getline(cin, s)) {
bool check = 1;
if (s == "0") break;
int sum = 0;
for (int i = 0; i < s.size(); i++) {
if (...C...) { // 判斷不是字母，提示：A~Z ascii為65~90, a~z ascii為97~122
cout << "多元選修好難喔" << endl;
check = 0;
break;
}
s[i] = toupper(s[i]);
sum += (...D...); // 計算題目所需的總和
}
if (!check) continue;
if (sum > 100) cout << "U should take a break" << endl;
else if (sum == 100) cout << "Perfect!" << endl;
else cout << sum << endl;
}
}
```
## p3. Towers of Hanoi
### 題目敘述
河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的，河內為越戰時北越的首都，即現在的胡志明市；1883年法國數學家 Edouard Lucas曾提及這個故事，據說創世紀時Benares有一座波羅教塔，是由三支鑽石棒（Pag）所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc），並命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅搬一個盤子，則當盤子全數搬運完畢之時，此塔將毀損，而也就是世界末日來臨之時。
### 輸入說明
每行有一個正整數$N$，代表有$N$個金盤
保證$N\le15$
### 輸出說明
三隻鑽石棒編號分別為$A,B,C$
請輸出將原本在$A$上的N個金盤移動至$C$上的最少步數方法
已知一開始$A$ 上的金盤最底層編號為$N$最上層編號為$1$
### 範例輸入
```=
1
2
3
```
### 範例輸出
```=
Move disc 1 from A to C
Move disc 1 from A to B
Move disc 2 from A to C
Move disc 1 from B to C
Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
```
- 試題內容
```cpp=
#include <iostream>
using namespace std;
void hanoi (int n, char from, char to) { // 第n個環從from移動至to
(...E...) return; // 返回條件
if (from == 'A' && to == 'B' || from == 'B' && to == 'A') {
hanoi (n - 1, from, 'C');
}
if (from == 'B' && to == 'C' || from == 'C' && to == 'B') {
hanoi (n - 1, from, 'A');
}
if (from == 'A' && to == 'C' || from == 'C' && to == 'A') {
hanoi (n - 1, from, 'B');
}
cout << "Move disc " << (...F...) << " from " << (...G...) << " to " << (...H...) << endl; // 輸出題目要求
if (from == 'A' && to == 'B' || from == 'B' && to == 'A') {
hanoi (n - 1, 'C', to);
}
if (from == 'B' && to == 'C' || from == 'C' && to == 'B') {
hanoi (n - 1, 'A', to);
}
if (from == 'A' && to == 'C' || from == 'C' && to == 'A') {
hanoi (n - 1, 'B', to);
}
}
int main() {
int n;
while (cin >> n) {
hanoi (n, 'A', 'C');
}
}
```
<!-- 進階班難度 -->
# 第二大題
## p4. 誰先晚餐
### Content
有 $n$ 個人來餐廳吃晚餐，第 $i$ 個人點的餐製作時間為 $t_i$ ，吃完他點的餐所需時間為 $e_i$
假設廚師只有一個同一時間只能準備一份餐點，且他在完成一份餐點後便能立刻開始製作下一份餐點，在每個人拿到他的餐點後便會立刻開始吃，吃完後就離開
請問在廚師選擇最佳的製作順序下，最後一個離開的人最早是多早?
### Input
多筆測資，第一行有一個整數 $n$ ，若讀到 $n=0$ 代表測資結束，不須對此筆輸入做出任何輸出。
接下來有$n$行每行兩個正整數 $t_i,e_i$ ，分別代表準備時間與食用時間。
20%測資符合 $n≤10$
40%測資符合 $n≤1000$
100%測資符合 $n≤105,1≤t_i,e_i≤105$
每個測資點不超過 $5$ 筆測資。
### Output
每筆測資輸出一行代表在最佳情況下，最後一個人的離開時間。
### Sample Input
```=
2
5 2
1 1
2
10 9
9 8
3
1 1
2 2
3 3
0
```
### Sample Output
```=
7
27
7
```
### Fill In The Blanks
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct order {int t, e;};
bool cmp(order a, order b) {
return (...A...);
}
int main() {
int n;
while (cin >> n, n) {
vector<order> vec(n);
for (auto& i : vec)
cin >> i.t >> i.e;
sort(vec.begin(), vec.end(), cmp);
long long cur = 0, maxn = 0;
for (const auto& i : vec)
cur += i.t, maxn = max(maxn, (...B...));
cout << maxn << endl;
}
return 0;
}
```
## p5. 翹好翹滿
### Content
每次上課太無聊的時候，如果老師要找公差，一定是一堆人舉手要去<sub>(翹課就是爽阿~)</sub>，而在一天當中可能會有很多次可以當公差的機會，
所以有可能一整天幾乎都不在教室 <sub>(那種感覺真是太棒拉~)</sub>
而現在如果給你一堆可以出公差的機會並且告訴你每份公差的開始時間及結束時間，在你選的公差時間都不重疊的情況下，
最多可以參加幾個公差?
### Input
第一行有一個正整數 $T$ 代表接下來有 $T$ 筆測資
每筆測資第一行有一個正整數 $n$ 代表共有 $n$ 個公差
接下來有$n$行每行兩個正整數 $l_i,r_i$ 分別每個公差的時間為 $(l_i,r_i)$ ，注意有些公差 $l_i=r_i$ ，也就是不需要消耗任何時間但是儘管它不需要消耗時間，你也不能在其他公差做到一半時偷跑來接這個公差。
$1≤T≤50 , 1≤n≤105 , 0≤l_i≤r_i≤109$
### Output
對於每筆測資輸出一行，代表最多能參加幾個公差。
### Sample Input
```=
2
3
1 4
3 6
6 8
5
0 5
3 7
8 10
5 10
1 3
```
### Sample Output
```=
2
3
```
### Fill In The Blanks
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct task {int l, r;};
bool cmp(task a, task b) {
return (...C...) || (a.r == b.r && (...D...));
}
inline void solve() {
int n; cin >> n;
vector<task> v(n);
for (auto& i : v)
cin >> i.l >> i.r;
sort(v.begin(), v.end(), cmp);
int cur = 0, cnt = 0;
for (const auto& i : v)
if (cur <= i.l)
cur = (...E...), cnt++;
cout << cnt << '\n';
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int T; cin >> T;
while (T--)
solve();
return 0;
}
```
Sign in with Wallet
Connect another wallet