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.
↵
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.
