There are 2 people who play a game. The game is as follows:
The are P sticks, each of length Q meters in length. The player play in turns. For each move a player choses a stick and splits it into 2 or more equal parts, each having an integer length greater than or equal to S meters. Each resulting part is also a stick. The player who can't make a move loses and the other player wins.
If both the players play optimally, determine the winner, given the values of P, Q and S.
For example : 2 1 15 4 4 9 5
Answer: Player 1 Player 2
Constrains: 1 <= T <= 10, the number of test cases 1 <= P, Q, S <= {10}9.
My approach till now: I was trying to solve this problem using grundy numbers. If the xor of grundy numbers of all piles is 0, player 2 is winner else player 1 is winner. Since all sticks are of same length, P = even number implies, player 2 is always the winner. When P = odd number, then if the grundy number of stick is 0, then player 2 is winner else player 1 is winner. The grundy is 0 only when all the proper divisors (i.e. except 1 and number itself) of the stick length are less than S.
Could anyone please verify whether my approach is correct or not?
Any help would be appreciated.
