---
# System prepended metadata

title: T26寒訓測機

---

# T26寒訓測機題解
## [codeforces](https://codeforces.com/contestInvitation/7c7a7c4c9d6737a6bafc2802ac7365e56a0b28b8)
## 比賽結束後仍然可以submit code

## A. Happy Chiense New Year
因為字串包含空格，所以記得用getline
::: spoiler 範例code by KCC
```cpp=
#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	getline(cin, s);
	cout << s << ", Happy Chiense New Year." << "\n";
	return 0;
}
```
:::

## C. add
原本要卡IO優化的，但沒有卡成功
:::spoiler 有IO優化

```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);
int main()
{
	KCC
	int n;
	cin >> n;
	long long sum = 0;
	for(int i = 0; i < n; i++){
		int a;
		cin >> a;
		sum += a;
	}
	cout << sum << "\n";
	return 0;
}
```
:::

:::spoiler 沒IO優化
```cpp=
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	long long sum = 0;
	for(int i = 0; i < n; i++){
		int a;
		cin >> a;
		sum += a;
	}
	cout << sum << "\n";
	return 0;
}
```
:::
  
## D. a/b
題目敘述很長，不要怕
要問a/b的最簡整數，所以就是約分就好，也就是找最大公因數
而C++有內建__gcd()可以用
::: spoiler 範例code by KCC

```cpp=
#include<bits/stdc++.h>
using namespace std;

int main()
{
	long long a, b;
	cin >> a >> b;
	cout << a / __gcd(a, b) << ' ' << b / __gcd(a, b) << "\n";
	
}
```
:::

## E. different prefix sum
這題比較難一點
可以發現 $n$ 必須放在第一個，為什麼?
因為 $n$ mod $n$ 為0也就是說如果不放在第一個，必定會出現重複的情況
例 : $n$ = 4時，2 3 4 1

再來思考一下$n$為奇數及偶數的情況

當 $n$ 是奇數則 1~n的和為 $n * (n + 1) / 2$
因為 $n$ 是奇數所以總和會變成 $n * k(k為(n + 1) / 2$ 後的值)
又$(n * k) mod$ $n = 0$，但因為0已經用過(因為$n$放第一個)，所以無法構造出一組合法的數列，其中1是特例

當$n$為偶數時則沒有此問題

所以可以想出 ~~(通靈)~~ 這樣的形式
:::success
n, 1, n - 2, 3, n - 4, 5...
:::

::: spoiler 範例code by KCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);

int main()
{
	KCC
	int n;
	cin >> n;
	if(n == 1){
		cout << "Yes" << "\n";
		cout << "1" << "\n";
	}
	else if(n % 2 == 1) cout << "No" << "\n";
	else{
		cout << "Yes" << "\n";
		for(int i = 0; i < n; i++){
			if(i % 2 == 0) cout << n - i << ' ';
			else cout << i << " ";
		}
	}
	return 0;
}
```
:::


## F. Hacker
可以觀察到這一行應該要有等號才對
:::warning
if(a > mod)a = a % mod;
:::
所以便可以用 a = 1e9+7, b = 1，來hack
::: spoiler 範例code by KCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);

int main()
{
	cout << 1000000007 << ' ' << 1 << "\n";
	return 0;
}
```
:::


## G. 42
gur Nafjre gb gur Hygvzngr Dhrfgvba bs Yvsr, gur Havirefr, naq Rirelguvat

這段文字是使用[凱薩加密](https://zh.wikipedia.org/zh-tw/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC)進行編碼，進行13位元的位移。
解密後的原文是：
"the Answers to the Ultimate Question of Life, the Universe, and Everything"

中文翻譯為：
"生命、宇宙和一切的終極問題的答案"

這是一個科幻小說的梗
[去看看](https://www.google.com/search?q=%E7%94%9F%E5%91%BD%E3%80%81%E5%AE%87%E5%AE%99%E5%92%8C%E4%B8%80%E5%88%87%E7%9A%84%E7%B5%82%E6%A5%B5%E5%95%8F%E9%A1%8C%E7%9A%84%E7%AD%94%E6%A1%88&rlz=1C1RXQR_zh-TWTW1017TW1017&oq=%E7%94%9F%E5%91%BD%E3%80%81%E5%AE%87%E5%AE%99%E5%92%8C%E4%B8%80%E5%88%87%E7%9A%84%E7%B5%82%E6%A5%B5%E5%95%8F%E9%A1%8C%E7%9A%84%E7%AD%94%E6%A1%88&gs_lcrp=EgZjaHJvbWUyBggAEEUYOTIKCAEQABiABBiiBDIKCAIQABiABBiiBDIKCAMQABiABBiiBNIBBzU5NWowajeoAgCwAgA&sourceid=chrome&ie=UTF-8)
:::spoiler 範例code by KCC
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define KCC ios::sync_with_stdio(0);cin.tie(0);

int main()
{
	cout << 42 << "\n";
	return 0;
}
```
:::

## H. 雞蛋
因為只能測31次，所以使用二分搜來找答案

::: spoiler 範例code by KCC
```cpp=
#include<bits/stdc++.h>
using namespace std;

int main()
{
	long long l = 1, r = INT_MAX;
	
	int a;
	while(l <= r){
		long long mid = (l + r) / 2;
		cout << "? " << mid << endl;
		
		cin >> a;
		if(a == 1) r = mid - 1;
		else l = mid + 1;
		cout << endl;
	}
	cout << "! " << l << endl;
}
```
:::



## 練習賽加油!!!!!

