time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Qc was asked to write a program to simulate a game "Guess a number". The program selects some integer number from 1 to q, and asks the player to find it. The program interacts with the player in the following way. The player inputs some integer number, and the program tells whether the player's number is equal, less than, or greater than the selected number. For example, for q = 8 the dialog could look in the following way:
- Player: 4 - Program: Greater than 4 - Player: 6 - Program: Less than 6 - Player: 3 - Program: Greater than 3 - Player: 5 - Program: Correct! It's 5. You have found it in 4 turns.
Using this simple game, people may, for example, study the method of binary search --- the optimal strategy to win with a minimal number of questions. The program was expected to work this way, but... Qc would not be himself if he did not bring us his new joke! Qc has intentionally inserted some bugs into his program, so that it worked a bit different compared to the way described above. The Qc Machine (as Qc has proudly called it) selects the number from 1 to q and asks the player to find it, but in the dialog the program does not answer the questions as expected. Instead the Qc machine answers the question that was asked c questions ago. So, after entering the i-th number, the player receives the information whether his (i-c)-th number was correct, less than, or greater than needed. For example, the algorithm, programmed in the Qc machine could have the following dialog with the player for q=21 and c=2:
- Player: 5 - Qc machine outputs nothing - Player: 9 - Qc machine outputs nothing - Player: 3 - Qc machine: Greater than 5 - Player: 7 - Qc machine: Less than 9 - Player: 6 - Qc machine: Greater than 3 - Player: 1 - Qc machine: Correct! It's 7. You have found it in 6 turns.
There were many attempts to find the optimal strategy in game with Qc's rules, but none of them was successful. Only Qc knows the optimal strategy, so your task for this contest is to find it, and for given q and c output the minimal number of steps required in the worst case to find the number selected by the Qc machine.
Input contains two integer numbers: q and c (1 <= q <= 10^15, 0 <= c <= 10^6).
Output a single integer n --- the number of questions required to find the selected integer number from 1 to q on the Qc machine with a delay parameter c in the worst case.
Test #1 21 2
Test #2 1 1
Test #3 65535 0
Test #4 65536 0
Test #5 111 1
Test #6 21 20
Test #1 10
Test #2 2
Test #3 16
Test #4 17
Test #5 11
Test #6 41
Anton Golubev, Petrazavodsk SU
Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
August 26, 2005
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov