## DMOPC '21 Contest 2 P3 - Divisions

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Alice is doing the DMOPC! The third problem reads as follows:

Given are two non-negative integers and . In one operation, you can halve the value of either or , rounding down. Compute the minimum number of operations required to make equal to .

Of course, Alice is a legendary programmer, so she instantly produces a program that solves the problem correctly for all pairs .

After the contest, while discussing the problem solutions with Alice, you somehow managed to leak to her the fact that you forgot the list of her favourite numbers!

"Zettai ni yurusanai wa!" she shouts. Of course, you have no idea what she just said (why would you), but it sounded quite serious. After a bit of a back and forth quarrel, you've managed to reach a compromise based on the program Alice wrote for the third problem.

In short, Alice allows you to make at most guesses in total for her list of favourite numbers , which you recall to be integers in the range . You will guess her list in increasing order of index, starting with . In each guess, if you are currently guessing the -th number, you must tell her an integer in the range and she will respond with the integer her program returns after plugging in and .

Given these conditions, please redeem yourself by correctly guessing Alice's favourite numbers!

#### Constraints

It is possible for the same number to appear more than once in Alice's list.

#### Interaction

At first, you should read in a line containing the integer .

You will then start the interaction by proceeding with your guesses, guessing first. Each guess should be formatted as a single integer followed by a \n character. If you are currently guessing the -th number, Alice will respond with a single line containing the integer her program returns after plugging in and .

If at any point Alice responds with , then you know that you have guessed the -th of her favourite numbers correctly and should move on to guessing the -th number. If she responds with for the -th time, then you know that you have guessed her entire list correctly and should terminate your program to receive an Accepted verdict.

However, if at any point you exceed the limit of guesses, is not an integer in the range , or your output is otherwise malformatted, Alice will respond with . You should terminate your program at this point to avoid receiving an arbitrary verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction

>>> denotes your output. Do not print this out.

In this case, Alice's list of favourite numbers is .

2
>>> 4
3
>>> 21
1
>>> 10
0
>>> 24
0

#### Explanation

For the first guess, Alice runs her program with and . Her program discovers that halving twice (rounding down) giving and halving once giving is the optimal solution to this case, equating and in operations total.

For the second guess, Alice runs her program with and . Halving once here (rounding down) gives in just operation, so Alice responds with .

For the third guess, Alice runs her program with and . Clearly no operations are needed here, so she responds with . Now that you've correctly guessed the first number, you should move on to guessing the second one.

For the fourth guess, Alice runs her program with and . No operations are needed here either, so she responds with . Now that you've correctly guessed all the numbers in no more than guesses, you should terminate your program to receive an Accepted verdict.