P9278 [AGM 2023 资格赛] 另一个游戏

解题思路

这是一道博弈论题，可以倒推求解：

1. 在只剩 $2$ 堆时获得先手，就能把第 $n-1$ 堆全部移完，把第 $n$ 堆留给对手，即可赢得比赛。
2. 为了在只剩 $2$ 堆时获得先手，要在只剩 $3$ 堆的时候获得先手，并移走第 $n-2$ 堆中的 $v_{n-2}-1$ 个，使对手只能移走最后 $1$ 个。
3. 不难发现，获得第 $k$ 堆的先手，就可以获得 $k+1$ 堆的先手。所以只要获得第 $2$ 堆的先手即可获胜。
4. 因为题目是将第 $1$ 堆移到第 $2$ 堆，且每一堆都是正整数，所以从第 $2$ 堆开始，后面不会出现只有 $1$ 个石子的情况。
5. Charlie 开局是先手，只要第 $1$ 堆不只 $1$ 个，都可以移走 $v_1-1$ 个，使 Dan 只能移走最后 $1$ 个。

综上所述，只要开局 $v_1\ne 1$，Charlie 都有必胜策略。特别地，当 $n=2$ 时只有两堆石子，Charlie 将第 $1$ 堆全部移完即可获胜。即当 $v_1\ne 1$ 或 $n=2$ 时输出 Charlie，否则输出 Dan。

参考代码

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

const int N=1005;
int v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>v[i];
	cout<<(v[1]!=1||n==2?"Charlie":"Dan")<<'\n';
	return 0;
}