[UVa1378][LA3668]有趣的石子游戏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file afunnystonegame.in Output file afunnystonegame.out

【题目描述】

有趣的石子游戏来了!有n堆石子,命名为0,1,2,...,n-1。两名玩家轮流捡石子。每一轮游戏,每名玩家选择三堆石子i,j,k(i<j,j<=k并且i中至少有一枚石子)。然后,这名玩家从第i堆中拿走一枚石子,并向第j堆和第k堆中各放入一枚石子。(如果j=k,就意味着向第j堆中放两枚石子)。无法按规则操作的玩家就输了。

David是先手并且他希望赢。你能写一个程序帮助他吗?

石子堆数n不超过23.每一堆的石子数不超过1000.假设对手非常聪明,会按照最佳方式操作。

【输入格式】

输入包含多组数据。

每组数据有两行。第一行有一个正整数n(1<=n<=23),表示石子堆数。第二行有n个空格隔开的非负整数S0,...,Sn-1(0<=Si<=1000),代表第0堆到第n-1堆的石子数量。

输入结束标志为一行一个0.

【输出格式】

对每组数据,按如下格式输出一行“Game t: i j k”。其中t是数据组数,i,j,k代表如果David想赢,他应该在第一步选择的三堆石子。如果有多组i,j,k,输出字典序最小的一组。如果他无法取胜,则i,j,k都是-1.

【样例输入】

4

1 0 1 100

3

1 0 5

2

2 1

0

【样例输出】

Game 1: 0 2 3

Game 2: 0 1 1

Game 3: -1 -1 -1

【来源】

UVa1378 A Funny Stone Game

LA3668 A Funny Stone Game

ACM ICPC 2006 Asia Regional Contest,Beijing: A Funny Stone Game