#bYybttg060702. 1664:【例 2】取石子游戏 2
1664:【例 2】取石子游戏 2
好的,我将这道题整理为清晰的题面格式,并补充样例解释、数据范围与时空限制:
题目描述
有一种有趣的游戏,玩法如下:
- 玩家: 人;
- 道具: 堆石子,每堆石子的数量分别为 ;
- 规则:
- 游戏双方轮流取石子;
- 每人每次选择一堆石子,并从中取走若干颗石子(至少取 颗);
- 所有石子被取完,则游戏结束;
- 如果轮到某人取时已没有石子可取,那此人算负。
假如两个游戏玩家都非常聪明,问谁胜谁负?
输入格式
第一行,一个整数 ;
第二行, 个空格间隔的整数 ,表示每一堆石子的颗数。
输出格式
输出仅一行,一个字符串,若先手获胜输出 win,后手获胜输出 lose。
样例
样例输入
4
7 12 9 15
样例输出
win
样例解释
这是一个经典的 Nim 游戏。
判断先手胜负的方法:计算所有石子数的异或(XOR)和:
- 如果 ,先手必胜(输出
win); - 如果 ,后手必胜(输出
lose)。
本题::
- (二进制:);
- ();
- ()。
,所以先手必胜,输出 win。
数据范围
对于全部数据:
时空限制
- 时间:
- 内存:
提示
这是博弈论中的 Nim 游戏 标准模型。
根据 Sprague–Grundy 定理,对于 Nim 游戏,定义 Nim-sum(所有堆石子数的异或和):
- 若 Nim-sum ≠ 0,先手有必胜策略;
- 若 Nim-sum = 0,后手有必胜策略。
复杂度 即可解决。