【bzoj1982】[Spoj 2021]Moving Pebbles

2014年3月22日1,8480

Description

2021. Moving Pebbles Two players play the following game. At the beginning of the game they start with n (1<=n<=100000) piles of stones. At each step of the game, the player chooses a pile and remove at least one stone from this pile and move zero or more stones from this pile to any other pile that still has stones. A player loses if he has no more possible moves. Given the initial piles, determine who wins: the first player, or the second player, if both play perfectly. 给你N堆Stone,两个人玩游戏. 每次任选一堆,首先拿掉至少一个石头,然后移动任意个石子到任意堆中. 谁不能移动了,谁就输了…

Input

Each line of input has integers 0 < n <= 100000, followed by n positive integers denoting the initial piles.

Output

For each line of input, output “first player” if first player can force a win, or “second player”, if the second player can force a win.

Sample Input

3 2 1 3

Sample Output

first player

题解

博弈论,因为这个游戏显然不同游戏之间会互相影响……不能用sg
所以推结论,容易发现n为奇数的时候,先手必胜
n为偶数的时候,先将石头排好序
后手必胜当且仅当对于所有i,第2i-1堆石头和第2i堆的数目相等

证明略
注意输入数据的石头数目非常坑……需要高精度
不过输入数据比较弱……
没有排序就能ac