Problem Statement Two players are playing a game. They have A bundles of pencils of size B each.
They also have a number C that they chose randomly. They move in turns and the person who's unable to make a move loses.
For each move a person chooses a bundle and divides it into some number (more than one) of equal parts/bundles, the size of each one is expressed by an integer and is no less than C.
Each resulting part is also a bundle which can be divided in future by any player.
Find the winner of the game.
Problem Constraints 1 <= A <= 105
1 <= B, C <= 109
Input Format First argument is the integer A.
Second argument is the integer B.
Third argument is the integer C.
Output Format Return 1 of the First player wins, 0 if Second player wins.
Example Input Input 1:
A = 4 B = 8 C = 6 Input 2:
A = 1 B = 9 C = 2
Example Output Output 1:
0 Output 2:
1
Example Explanation Explanation 1:
Player 1 cannot divide any of the bundle, so that the divided bundles have size not less than 6. Hence he loses. Explanation 2:
They have only 1 bundle to start with. Player 1 has only one valid move where he divides this bundle into 3 bundles of size 3. After this Player 2 cannot divide bundles of size 3 further. Hence Player 2 loses.
Intuition
if A is even, player2 wins because player2 can mimic player1's move. But what if A is odd?
It's a Nim game: https://codeforces.com/blog/entry/66040
But the operation is different than Nim Game. So how would it be solved for a game with odd number of piles?
Read the post I linked to. It can be generalized.
Are you referring to this problem? https://codeforces.com/problemset/problem/78/C
That player 2 always wins if $$$A$$$ is even is a great first step! In fact, you're almost done. The case for when $$$A$$$ is odd is not too far from that, and I suggest you think about it some more before looking at the problem's editorial.