dumb_fish's blog

By dumb_fish, history, 4 years ago, In English

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?

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But the operation is different than Nim Game. So how would it be solved for a game with odd number of piles?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Read the post I linked to. It can be generalized.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.