Guessing Game

View as PDF

Submit solution

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

Problem type

Here is a popular guessing game when your CS teacher introduces binary search: given a goal number N (hidden) and a range (X, Y) containing it (not including X and Y), everyone takes turns to guess what N is. Following every wrong guess, the range shrinks to a new range with either X or Y replaced by the guessed number. The game ends when a guess hits the number N. 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 N is 25 and the range is (X=1, Y=99), the first guess would be 50 which doesn't hit; the range then shrinks to (1,50); the second guess would be 25 which hits the goal. The number of rounds is therefore 2.

Input Specification

The input contains three integers N, X, and Y, (1 \le X < N < Y \le 10\,000), where N is the goal number and (X, Y) is the initial range.

Output Specification

The number of rounds that need to be played.

Sample Input 1

25 1 99

Sample Output 1


Sample Input 2

77 30 100

Sample Output 2



There are no comments at the moment.