Guessing Game

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Here is a popular guessing game when your CS teacher introduces binary search: given a goal number (hidden) and a range containing it (not including and ), everyone takes turns to guess what is. Following every wrong guess, the range shrinks to a new range with either or replaced by the guessed number. The game ends when a guess hits the number . Supposing that everyone always guesses the median of the range (if there are two, choose the smaller one), how many rounds need to be played for the game to end?

For example, if is and the range is , the first guess would be which doesn't hit; the range then shrinks to ; the second guess would be which hits the goal. The number of rounds is therefore .

Input Specification

The input contains three integers , , and , , where is the goal number and is the initial range.

Output Specification

The number of rounds that need to be played.

Sample Input 1

25 1 99

Sample Output 1

2

Sample Input 2

77 30 100

Sample Output 2

4