Problem E
Cracking a Password

We finally accessed one of the AI Overlords’ data servers, and there’s just one level of security left to get through. We know the password is a 15 digit hexadecimal number, and a poorly designed password checker will let you know if we guessed the password correctly, if the number is larger, or if it is smaller. However, we can only make 61 queries before we’re locked out.

This is an interactive problem. This means that the input to your program will change based on what your program outputs.

Hexadecimal is a way of writing integers using $16$ values, instead of $10$. The distinct values used in hex are the standard base-$10$ values $0$-$9$, as well as $A, B, C, D, E$, and $F$ in that order, with $A$ having value $10$, $B$ having value $11$, up to $F$ having value $15$. A hexadecimal number can be translated to the standard base-$10$ format as follows: if our hex number is written as $a_n a_{n-1} ... a_1 a_0$, then its value is equal to

For example, the hex number $1FA$ is equal to $1 \cdot 16^2 + 15 \cdot 16 + 10 = 506$.

Similarly, a base-$10$ number can be translated in hex as follows: if $x_0$ is the number, then the last digit of the hex number is the remainder of $x_0$ when divided by $16$. Define $x_{n+1}$ as $x_n$ divided by $16$ and rounded down, and repeat this process, building the hex representation of $x_0$ one digit at a time. Once $x_n = 0$, you are done translating the number into hexadecimal.

For example, say we want to translate $x_0 = 483$ into hexadecimal. This number’s remainder when divided by $16$ is $3$, so this is the last value in the hexadecimal representation. Dividing $x_0$ by $16$ and rounding down yields $x_1 = 30$. This has remainder $14$ when divided by $16$, and $14$ is represented as $E$ in hexadecimal. Dividing $x_1$ by $16$ and rounding down yields $x_2 = 1$. Since this number, once divided by $16$ and rounded down, is $0$, this means the process terminates. So, the hexadecimal representation of $483$ is given by $1E3$.

Interaction

You may make guesses of the form ? a, where $a$ is a hexadecimal number with 15 digits. Pad the front of the number with zeroes if it can be written with fewer than 15 digits. (So, if your hexadecimal guess is $1E3$, instead print $0000000000001E3$.)

Remember to flush your output after making a query.

    cout.flush(); // C++
    System.out.flush(); // Java
    print(..., flush=True) # Python

After each guess, I will respond with one of the following.

• That's correct! — You found the password!

• Too low! — Your guess is lower than the password.

• Too high! — Your guess is higher than the password.

Your program should exit after receiving a response of That's correct!.

Your submission will receive a Wrong Answer verdict if you make more than $61$ queries or if any of your queries are not a 15 digit hexadecimal string.

If the interactor receives any invalid input, the interactor will output $-1$ and then immediately terminate. Your program should cleanly exit in order to receive a Wrong Answer verdict, otherwise the verdict that it receives may be an arbitrary verdict indicating that your submission is incorrect.

You are provided with a command-line tool for local testing (see the attachments at the bottom of this page). The tool has comments at the top to explain its use.

Explanation of sample interaction

The first guess made by the program was reported as being too large. A smaller number was then guessed, which was reported as being too low. Luckily, the next guess happened to be correct, after which the program terminated.

? DF545B46CD800B7

Too high!

? D769AF736EA91CF

Too low!

? DEC0DEDDEADBEEF

That's correct!