The beauty of a number X is the number of 1s in the binary representation of X.
Two players are plaing a game. There is number n written on a black board. The game is played as following:
Each time a player chooses an integer number (0 <= k) so that 2^k is less than n and (n-2^k) has as beautiful as n. Next he removes n from blackboard and writes n-2^k instead. The player that can not continue the game (there is no such k that satisfies the constrains) looses the game.
The First player starts the game and they play in turns alternatively. Knowing that both two players play optimally you have to specify the winner.
Input:
First line of the Input contains an integer T, the number of testcase. 0 <= T <= 5.
Then follow T lines, each containing an integer n.
n more than 0 and less than 10^9 +1.
Output
For each testcase print "First Player" if first player can win the game and "Second Player" otherwise.
Sample Input
7
1
2
8
16
42
1000
123
Sample Output
Second Player
First Player
First Player
Second Player
Second Player
First Player
Second Player
Explanation
In the first example n is 1 and first player can't change it so the winner is the second player.
In the second example n is 2, so the first player subtracts 1 (2^0) from n and the second player looses the game.
Anyone Please ..
As k is small (less than 30) and the number of allowed moves for each n is rather small too (if ith bit of n is 1, you can't subtract 2^i; also not all "zeroes" are available too), the overall amount of states (n,k) you can obtain can be also not so big, so you can try dp on map.
I implemented your idea , but i am getting TLE .
Code
http://ideone.com/bo1Ma2
And what is TL for this problem? Maybe optimizing of calculating the beauty can help you — you can also precalc it for all numbers up to 10M, for example.
UPD. If you go only into zeroes which stand immediately after ones, as riadwaw said, it doesn't get TLE in Ideone: http://ideone.com/oK0fwy
I improved it to 0.25 Sec by breaking for loop in solve() immediately after i found a losing position . http://ideone.com/3OERdw
That's cool:) Does it decrease the amount of overall states in 20 times?..
It's possible to use unordered_map, it may be faster.Doesn't help
Usually solution to this type of problem goes like this: Do DP for numbers 1 — 200, print solutions and find pattern.
You should only choose 0-s that are after 1-s, after that you sholdn't calculate beauty.
Ex:
After that it seems, it's not important how game are played and answer only depends of pairity (sum_of_number_of_position_of_ones — sum(0...n — 1)) where n is the number of ones.
"You should only choose 0-s that are after 1-s"
Why should we leave other possible moves ..??
See, if we choose 1, it's disappered. It's bad.
If we choose 0 consider nearest 1 on the left.
(first)100000(second) ^ choose itAfter subtraction it will look like
one 1 is disappeared, and [distance between chosen pos and pos of this 1] of 1's appered. So distance should be 1.
actually choosing such k where (n-2^k) have the same beauty that means moving one of 1's bits one step to right for example let n=1000100 (in binary) you can either choose k=1 then n-2^k=1000010 or k=5 so n-2^k=0100100, there is no anothor valid value for k in the position.
I think the problem is too easy now :)