OI题库

【题目描述】

有趣的石子游戏来了！有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