DMOPC '17 Contest 2 P5 - Game

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

You are playing a game with your friend. There is a pile with N stones and a chosen number K. You and your friend alternate turns to remove some number of stones. Call s_i the number of stones removed on the i^\text{th} turn. s_1=1, that is, the first player must remove exactly 1 stone. After that, on the i^\text{th} turn, the current player is allowed to remove any number of stones between 1 and s_{i-1}+K. The player who removes the last stone wins. Given that you are the first player, for how many possible N between X and Y inclusive can you guarantee a win?

Constraints

For all subtasks:

1 \le K \le 10^{15}

Subtask 1 [10%]

1 \le X, Y \le 100

Subtask 2 [10%]

1 \le X, Y \le 5\,000

Subtask 3 [40%]

1 \le X, Y \le 1\,000\,000

Subtask 4 [40%]

1 \le X, Y \le 10^{15}

Input Specification

The first line will have three space-separated integers, K, X, and Y in that order.

Output Specification

Output the answer.

Sample Input

5 11 41

Sample Output

6

Comments

There are no comments at the moment.