OCC '19 B6 - Fiji water

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.5s
Memory limit: 64M

Problem type

Winnie and Modo are playing a game together with N bottles of Fiji water. Each turn, they can take either 1 bottle or Z bottles, where Z is a power of Y. The player who takes the last bottle loses. If both players play optimally, who will win the game? Winnie makes the first move.

Input Specification

The first line will contain N and Y, the number of bottles of Fiji Water and the power for the amount of bottles you can take, respectively.

Output Specification

Output the winner of the game if both players play optimally.


For all subtasks:

1 \le N, Y \le 10^9

Subtask 1 [20%]

1 \le N \le 10^5

1 \le Y \le 10^4

Subtask 2 [80%]

No additional constraints.

Sample Input 1

4 2

Sample Output 1


Explanation 1

Winnie can take 1, 2 or 4 bottles. If Winnie takes 4 bottles, she loses because she took the last bottle. If Winnie takes 2 bottles, Modo can take 1 bottle, forcing Winnie to take the last bottle. If Winnie takes 1 bottle, Modo can take 2 bottles and force Winnie to take the last bottle. Modo will always win if she plays optimally.

Sample Input 2

10 3

Sample Output 2


Explanation 2

Winnie can take 9 bottles, forcing Modo to take the last bottle.


There are no comments at the moment.