35015번 - Collatz Hypothesis and Random Increases 다국어인터랙티브

문제

This is an interactive problem.

We define the Collatz function $\mathrm{collatz}(x)$ which operates on integers as follows: if $x$ is even, then $\mathrm{collatz}(x) = \frac{x}{2},ドル and otherwise $\mathrm{collatz}(x) = 3x + 1$. The famous Collatz hypothesis states that if you start with any positive integer $x_0$ and construct a sequence $x_1 = \mathrm{collatz}(x_0),ドル \ldots, $x_{i + 1} = \mathrm{collatz}(x_i),ドル then the sequence will eventually reach the number one.

The incredible complexity that has kept the hypothesis neither proven nor disproven lies in the very chaotic behavior of the sequence $\left\{x_i\right\}$ until it reaches one. Even for very small numbers, one can reach the number one quite late: for example, starting with $x_0 = 9,ドル we get $9ドル \to 28 \to 14 \to 7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1\text{,}$$ and if we start with $x_0 = 27,ドル we only reach one after 111 applications of $\mathrm{collatz}(x)$!

You are sitting in front of a machine that has a screen and two buttons: red and blue. The screen displays a positive integer (it is guaranteed to be a random integer from 2ドル$ to 10ドル^7,ドル inclusive), and you need to turn it into one. The red button is called collatz, and it replaces the number $x$ on the screen with $\mathrm{collatz}(x)$. The blue button is called random, and it replaces $x$ with a random integer from 3ドルx + 1$ to 6ドルx,ドル inclusive. Pressing the buttons is not free: after each button press, when the screen displays the number $x_{i + 1},ドル you need to insert as many tokens into the machine as there are digits in the decimal representation of the number $x_{i + 1}$. For example, in the above process starting from nine, you need to pay for all the digits of the numbers 28,ドル 14, 7, \ldots, 2, 1$; this will cost you 32 tokens.

If you only press the red button, you will reach one, spending an average of 707 tokens. Although the blue button always increases the number on the screen (and significantly), you can speed up the process of reaching one by pressing the blue button at the right moments! Your task is to write a program that spends on average no more than 600 tokens for a single number. To reduce the randomness in the checks, we will provide the program with $t \le 50$ random starting numbers in each test, and you need to turn all of them into ones for a total of 600ドル \cdot 50 = 30,000円$ tokens.

입력

출력

제한

인터랙션 프로토콜

First, read a line containing an integer $t$: the number of starting numbers (1ドル \le t \le 50$). The jury has $t$ starting numbers $x_0,ドル selected uniformly and independently at random from the range $\left[2; 10^7\right],ドル and you need to turn them all into ones in sequence.

At the beginning of the $i$-th round, read a line containing a single integer $x_0$: the next starting number (2ドル \le x_0 \le 10^7$). Then you need to transform the number. After each transformation, if the screen shows the number $x_j,ドル output a line with either the string "collatz" (the letters can be in any case) if you want to replace the number with $x_{j+1} = \mathrm{collatz}{\left(x_j\right)},ドル or the string "random" (the letters can be in any case) if you want to replace the number with $x_{j+1}$ which is a random integer uniformly selected from the range $\left[3x_j+1; 6x_j\right]$. After printing each line, do not forget to flush the output buffer, otherwise, you will likely receive an error of Idleness Limit Exceeded:

• std::cout.flush() in C++;
• fflush(stdout) in C;
• stdout.flush() in Python and D;
• flush(output) in Pascal and Delphi;
• System.out.flush() in Java;
• for help with other languages, refer to the documentation.

After that, read a line containing a single integer $x$. The following options are possible:

• if $x = 0,ドル you have run out of tokens;
• if $x = 1,ドル then $x_{j+1}=1$: you have successfully completed the round, move on to the next round (for which you should start by reading the next starting number $x_0$);
• if $x > 1,ドル then $x_{j+1}=x$: the number on the screen has changed after pressing the button, continue outputting the strings "collatz" and "random". Note that, during the interaction, $x$ may exceed 2ドル^{64}$ as well as 2ドル^{128}$.

The jury will also send your program the number 0ドル$ if you violate the output format and print any string other than "collatz" and "random". Upon reading 0ドル,ドル your program should immediately terminate to receive a Wrong Answer verdict. Otherwise, the verdict can be anything other than Accepted.

After reading the $t$-th number one, terminate the program to receive the Accepted verdict.

노트

The example is the only test where the starting numbers $x_0$ are chosen not randomly, but manually.