# 2024/11/08 打學弟的期中考

## 前言

**因為是打學弟的考試，所以沒啥心得可講**
**這篇大概純題解 + 個人一些看法**
**然後是過了半年才補的文，所以看看就好。**

## 題目

### pA

:::success
**給你長度為 $3$ 的字串**
**求他的全排列有多少種**
:::

:::spoiler **想法 + 作法**
1. **直接 `next_permutation` 硬砸**
2. **排列組合 - 吃力不討好**
:::

:::spoiler **code**

#include <iostream>
#include <algorithm> // sort
using namespace std;
int main() {
    string s; cin >> s;
    sort(s.begin(), s.end());
    int ans = 0;
    do {
        ans++;
    } while(next_permutation(s.begin(), s.end()));
    cout << ans << '\n';
}

:::

### pB

:::success
**輸入好多個東西，然後在中間間隔逗點**
:::

:::spoiler **想法+作法**
**`while(cin>>s)`**
**`bool`紀錄是不是第一個輸入進來的字串**
:::

:::spoiler **code**

#include <iostream>
using namespace std;
int main() {
    string s; bool first = true;
    while(cin >> s) {
        if(first) first = false;
        else cout << ",";
        cout << s;
    }
    cout << '\n';
}

:::

:::warning
**這題是嚴格比對 :(**
**要輸出 `\n`**
:::

### pC

:::success
**有 $N$ 道菜 $A_i$**
**$M$ 天要吃一道菜 $B_j$**
**一道菜只能吃一次，有一天吃不到就算計畫失敗**
**問計畫有沒有成功**
:::

:::spoiler **想法+作法**
**先開一個陣列將菜都存進來**
**每一天都掃過去，假如有就拿走 (順便把那道菜設成 -1\[不可能的狀態\])**
:::

:::spoiler **code**

#include <iostream>
using namespace std;
int v[1000];
int main() {
	int n, m; cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> v[i];
	bool ok = true;
	for(int j = 0; j < m; j++) {
		int a; cin >> a;
		bool found = false;
		for(int k = 0; k < n; k++) {
			if(v[k] == a) {
				found = true;
				v[k] = -1; // remove the dish
				break; // important
			}
		}
		if(!found) ok = false;
	}
	if(ok) cout << "Yes\n";
	else cout << "No\n";
}

:::

### pD

:::success
**一開始有 $A$ 個史萊姆**
**每次分裂變 $K$ 倍**
**要多少次到達 $B$**
:::

:::spoiler **想法 + 作法**
**`for`或`while`迴圈暴過去**
:::

:::spoiler **code**

#include <iostream>
using namespace std;
int main() {
	long long a; // a*k will overflow
	int b, k; cin >> a >> b >> k;
	int ans = 0;
	while(a < b) ans++, a *= k;
	cout << ans << '\n';
}

:::

:::spoiler **bonus - 神奇的解法**
**假如你數學特別強，那你肯定知道高中生必學的換底公式**

$$
\log_b{a} = \frac{\log_{c}{a}}{\log_{c}{b}} = \frac{\log_{10}{a}}{\log_{10}{b}} = \frac{\log_{e}{a}}{\log_{e}{b}}
$$

**所以可以 $O(1)$ 時間數學解這題**

> $O(...)$ 為複雜度，有興趣可以去看演算法入門

**然後題目就被轉化為**

$$
ans = \log_k{\lceil \frac{b}{a} \rceil}
$$

#include <iostream>
#include <cmath> // ceil logl
using namespace std;
int main() {
	int a, b, k; cin >> a >> b >> k;
	cout << ceil(logl((b+a-1)/a)/logl(k)) << '\n';
}

**但記得要加 $logl$ 不然C++小數精準度太爛，會吃WA**
:::

## 總結

**作為期中考，pC確實有點難度了，畢竟吃到了陣列**
**pB 大部分的人應該是卡在`while(cin>>s)`**
**pA 高一這時候應該沒學過排組，但 $3!$ 應該if砸一砸就有**
**pD overflow 有點搞人，但吃WA開long long很合理**