#bYybttg060702. 1664:【例 2】取石子游戏 2

1664:【例 2】取石子游戏 2

好的,我将这道题整理为清晰的题面格式,并补充样例解释、数据范围与时空限制:


题目描述

有一种有趣的游戏,玩法如下:

  • 玩家:22 人;
  • 道具:NN 堆石子,每堆石子的数量分别为 X1,X2,,XNX_1, X_2, \dots, X_N
  • 规则:
    1. 游戏双方轮流取石子;
    2. 每人每次选择一堆石子,并从中取走若干颗石子(至少取 11 颗);
    3. 所有石子被取完,则游戏结束;
    4. 如果轮到某人取时已没有石子可取,那此人算负。

假如两个游戏玩家都非常聪明,问谁胜谁负?


输入格式

第一行,一个整数 NN

第二行,NN 个空格间隔的整数 XiX_i,表示每一堆石子的颗数。


输出格式

输出仅一行,一个字符串,若先手获胜输出 win,后手获胜输出 lose


样例

样例输入

4
7 12 9 15

样例输出

win

样例解释

这是一个经典的 Nim 游戏

判断先手胜负的方法:计算所有石子数的异或(XOR)和:

S=X1X2XNS = X_1 \oplus X_2 \oplus \dots \oplus X_N
  • 如果 S0S \neq 0,先手必胜(输出 win);
  • 如果 S=0S = 0,后手必胜(输出 lose)。

本题:7129157 \oplus 12 \oplus 9 \oplus 15

  • 712=117 \oplus 12 = 11(二进制:01111100=1011=110111 \oplus 1100 = 1011 = 11);
  • 119=211 \oplus 9 = 210111001=0010=21011 \oplus 1001 = 0010 = 2);
  • 215=132 \oplus 15 = 1300101111=1101=130010 \oplus 1111 = 1101 = 13)。

S=130S = 13 \neq 0,所以先手必胜,输出 win


数据范围

对于全部数据:

  • N5×104N \le 5 \times 10^4
  • 1Xi1051 \le X_i \le 10^5

时空限制

  • 时间:1000 ms1000 \text{ ms}
  • 内存:524288 KB524288 \text{ KB}

提示
这是博弈论中的 Nim 游戏 标准模型。
根据 Sprague–Grundy 定理,对于 Nim 游戏,定义 Nim-sum(所有堆石子数的异或和):

  • 若 Nim-sum ≠ 0,先手有必胜策略;
  • 若 Nim-sum = 0,后手有必胜策略。

复杂度 O(N)O(N) 即可解决。