取火柴游戏

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 matchi.in 输出文件 matchi.out

【问题描述】

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

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

    例如:k2n1n22A代表你,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”。

【样例1

match.in                 match.out

3                        4 3 {表示第一次从第3堆取4个出来,必胜}

3 6 9                    3 6 5 {第一次取后的状态}

【样例2

match.in                  match.out

4                         lose {先取必败}

15 22 19 10