U525097 【模板】nim(调用式交互)
题目背景
ALANYQ 在 OI 时闲着没事就会打开 Python 玩 nim,~~每次都被 Python “打败”~~。
ALANYQ 希望你帮他找出必胜策略,教他获胜。
题目描述
**本题是交互题,请认真阅读题目要求!**
**玩法说明**:有 $n$ 堆石子,序号为 $1\sim n$。第 $i$ 堆有 $a_i$ 个石子,每次操作可从某一堆中取走任意个(必须取走),最后无石子可取的人输。
你是先手。且每次你取走石子后,评测机将以最优策略取石子。保证评测机取走的石子合法。
你可**直接调用**的交互库函数:
1. **`long long get_num()`**:获取石子堆数;
2. **`bool is_win()`**:获取是否结束($0$ 为游戏没有结束,$1$ 为已经结束)。
3. **`bool take_stone(long long n, long long i)`**:两个参数分别代表取走的堆号、取走个数。返回值:$1$ 代表取走成功,$0$ 代表取走失败。
4. **`vector get_stone()`**:获取每堆还剩下多少石头。
**因不明原因,本题请勿使用 `for (auto i : stones)`!**
输入格式
无
输出格式
无
说明/提示
### 样例解释
:::info[双方的最优策略]
1. 用户将第 $3$ 堆的石子取走 $2$ 个,此时石头数为 $3, 3, 1$;
2. 评测机将第 $1$ 堆的石子取走 $2$ 个,此时石头数为 $1, 3, 1$;
3. 用户将第 $2$ 堆的石子取完,此时石头数为 $1, 0, 1$;
4. 评测机将第 $1$ 堆的石子取完,此时石头数为 $0, 0, 1$;
5. 用户将第 $3$ 堆的石子取完,此时石头数为 $0, 0, 0$;
评测机没有石头可取,因此用户赢了。
:::
### 数据点信息
对于每个测试点的内容,你均无需输入,也无需输出,直接调用函数即可。
如果你赢了,该测试点满分;否则该测试点 Wrong Answer $0$ 分。
**开启捆绑测试!**
:::info[测试点信息]
| 子任务 | 分数 | $n$ | $a_i$ | 个数 | 时限 |
| :-: | :-: | :-: | :-: | :-: | :-: |
| # $1$ | $5$ pts | $\le 100$ | $\le 100$ | $5$ | $100$ ms |
| # $2$ | $10$ pts | $\le 500$ | ^ | ^ | ^ |
| # $3$ | $15$ pts | $\le 10^3$ | ^ | ^ | ^ |
| # $4$ | $25$ pts | $\le 10^4$ | $\le 10^3$ | $3$ | $200$ ms |
| # $5$ | $45$ pts | $\le 10^5$ | ^ | $2$ | ^ |
对于所有数据,$1\le a_i\le 10^3$,$1\le n\le 10^5$,保证所有的数据均有必胜策略,且经过验证先手存在必胜策略。
:::
### 函数模板
```cpp
#include
#include
extern "C" { // 声明交互库函数
extern void play();
long long get_num();
std::vector get_stone();
bool take_stone(long long n, long long i);
bool is_win();
}
extern "C" void play() {
long long n = get_num();
while (!is_win()) {
}
}
```
注:交互库没有 `using namespace std;`,请自行添加在代码中。