NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem100--取火柴游戏

100: 取火柴游戏

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

输入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”。


Input

第一行,一个正整数k。

第二行,k个整数n1,n2,…,nk。

Output

如果是先取必胜,请在第一行输出两个整数a,b,表示第一次从第b堆取出a个。第二行为第一次取火柴后的状态。如果有多种答案,则输出<b,a>字典序最小的答案(即b最小的前提下a最小)。

如果是先取必败,则输出“lose”。

Sample Input Copy

3
3 6 9

Sample Output Copy

4 3
3 6 5

HINT

【数据规模】

k<=500000;

ni<=1e9;

Source/Category

其他