5817 - 取火柴游戏

通过次数

16

提交次数

34

时间限制 : 1 秒
内存限制 : 64 MB

输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni。接着便是和计算机对弈游戏,取火柴的规则如下:每次可以从一堆中取走若干根火柴,也可以将一堆全部取走,但不允许跨堆取,也不允许不取。

谁取走最后一根火柴算谁胜利。

例如,k=2,n1=n2=2,A代表你,P代表计算机,若决定A先取:

A:(2,2)→(1,2)   ∥从一堆中取一根

P:(1,2)→(1,1)   ∥从另一堆中取一根

A:(1,1)→(1,0)

P:(1,0)→(0,0)   ∥P胜利

如果决定A后取:

P:(2,2)→(2,0)

A:(2,0)→(0,0)   ∥A胜利

又如k=3,n1=1,n2=2,n3=3,A决定后取:

P:(1,2,3)→(0,2,3)

A:(0,2,3)→(0,2,2)

A已将游戏归结为(2,2)的情况,不管P如何取A都必胜。

编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜,请输出第一次该如何取。如果是先取必败,则输出“lose”。

输入

 

输出

 

样例

输入

3
3 6 9

输出

4 3   //表示第1次从第3堆取4个出来必胜
3 6 5  //第1次取后的状态

输入

4
15 22 19 10

输出

lose   //先取必败

来源

课课通