codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2109C1.md (6101B)


      1 Source: https://codeforces.com/problemset/problem/2109/C1
      2 
      3 C1. Hacking Numbers (Easy Version)
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is the easy version of the problem. In this version, you can send at most $\mathbf{7}$ commands. You can make hacks only if all versions of the problem are solved.
     22 
     23 This is an interactive problem.
     24 
     25 Welcome, Duelists! In this interactive challenge, there is an unknown integer $x$ ($1 \le x \le 10^9$). You must make it equal to a given integer in the input $n$. By harnessing the power of "Mathmech" monsters, you can send a command to do one of the following:
     26 
     27 |  |  |  |  |  |  |
     28 | --- | --- | --- | --- | --- | --- |
     29 | Command | Constraint | Result | Case | Update | Jury's response |
     30 | "add $y$" | $-10^{18} \le y \le 10^{18}$ | $\mathrm{res} = x + y$ | $\text{if } 1 \le \mathrm{res} \le 10^{18}$ | $x \leftarrow \mathrm{res}$ | "1" |
     31 | $\mathrm{else}$ | $x \leftarrow x$ | "0" |
     32 | "mul $y$" | $1 \le y \le 10^{18}$ | $\mathrm{res} = x \cdot y$ | $\text{if } 1 \le \mathrm{res} \le 10^{18}$ | $x \leftarrow \mathrm{res}$ | "1" |
     33 | $\mathrm{else}$ | $x \leftarrow x$ | "0" |
     34 | "div $y$" | $1 \le y \le 10^{18}$ | $\mathrm{res} = x/y$ | $\text{if } y$ divides $x$ | $x \leftarrow \mathrm{res}$ | "1" |
     35 | $\mathrm{else}$ | $x \leftarrow x$ | "0" |
     36 | "digit" | — | $\mathrm{res} = S(x)$$^{\text{∗}}$ | — | $x \leftarrow \mathrm{res}$ | "1" |
     37 
     38 You have to make $x$ equal to $n$ using at most $\mathbf{7}$ commands.
     39 
     40 $^{\text{∗}}$$S(n)$ is a function that returns the sum of all the individual digits of a non-negative integer $n$. For example, $S(123) = 1 + 2 + 3 = 6$
     41 
     42 Input
     43 
     44 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.
     45 
     46 The first and only line of each test case contains one integer $n$ ($1 \le n \le 10^9$).
     47 
     48 Interaction
     49 
     50 The interaction for each test case begins by reading the integer $n$.
     51 
     52 To send a command, output a line in the following format:
     53 
     54 * "add $y$" Add some integer $y$ ($-10^{18} \le y \le 10^{18}$) to $x$.
     55 
     56   The jury will output "1" if $x + y$ is within $[1, 10^{18}]$ (successful), and "0" otherwise. If successful, update $x \leftarrow x + y$.
     57 * "mul $y$" Multiply $x$ by a positive integer $y$ ($1 \le y \le 10^{18}$).
     58 
     59   The jury will output "1" if $x \cdot y$ is within $[1, 10^{18}]$ (successful), and "0" otherwise. If successful, update $x \leftarrow x \cdot y$.
     60 * "div $y$" Divide $x$ by a positive integer $y$ ($1 \le y \le 10^{18}$).
     61 
     62   The jury will output "1" if $y$ is a divisor of $x$ (successful), and "0" otherwise. If successful, update $x \leftarrow \frac{x}{y}$.
     63 * "digit" Make $x$ equal to the sum of its digits.
     64 
     65   The jury will always output "1" and update $x \leftarrow S(x)$.
     66 
     67 Note that commands are case sensitive.
     68 
     69 When you have determined that $x$ is equal to $n$, output a line in the following format:
     70 
     71 * "!" — where the jury will output a "1" if $n$ is equal to $x$, and "-1" otherwise.
     72 
     73 Note that answering does not count toward your limit of $\mathbf{7}$ commands.
     74 
     75 If your program makes more than $\mathbf{7}$ commands for one test case, or makes an invalid command, then the response to the command will be "-1". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
     76 
     77 After printing a command, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
     78 
     79 * fflush(stdout) or cout.flush() in C++;
     80 * System.out.flush() in Java;
     81 * sys.stdout.flush() in Python;
     82 * std::io::stdout().flush() in Rust;
     83 * see the documentation for other languages.
     84 
     85 The interactor is non-adaptive. The unknown integer $x$ does not change during the interaction.
     86 
     87 Hacks
     88 
     89 To hack, use the following format.
     90 
     91 The first line should contain a single integer $t$ ($1 \leq t \leq 5000$) — the number of test cases.
     92 
     93 The first line of each test case should contain two positive integers $n$ and $x$ ($1 \leq n,x \leq 10^9$) — denoting the unknown integer and the target value to which it should be made equal, respectively.
     94 
     95 Example
     96 
     97 Input
     98 
     99 ```
    100 2
    101 100
    102 
    103 0
    104 
    105 1
    106 
    107 1
    108 
    109 1
    110 
    111 5
    112 
    113 1
    114 
    115 1
    116 
    117 1
    118 ```
    119 
    120 Output
    121 
    122 ```
    123 add -10
    124 
    125 add 1
    126 
    127 mul 10
    128 
    129 !
    130 
    131 digit
    132 
    133 div 2
    134 
    135 !
    136 ```
    137 
    138 Note
    139 
    140 |  |  |  |
    141 | --- | --- | --- |
    142 | Solution | Jury | Explanation |
    143 |  | $\texttt{2}$ | There are 2 test cases. |
    144 |  | $\texttt{100}$ | In the first test case, the unknown integer $x = 9$ and we have to make it equal to $n = 100$. |
    145 | $\texttt{add -10}$ | $\texttt{0}$ | The answer to "add -10" is "0". This means that the addition command was not successful as $x + y = 9 + (-10) \le 0$, and $x$ remains $9$ after the command |
    146 | $\texttt{add 1}$ | $\texttt{1}$ | The answer to "add 1" is "1". This means that the addition command was successful as $x + y = 9 + 1 = 10$, and $x$ changes to $10$ after the command. |
    147 | $\texttt{mul 10}$ | $\texttt{1}$ | The answer to "mul 10" is "1". This means that the multiplication command was successful as $x \cdot y = 10 \cdot 10 = 100$, and $x$ changes to $100$ after the command. |
    148 | $\texttt{!}$ | $\texttt{1}$ | The answer to "!" is "1". This means you have determined that $x$ equals $n$. |
    149 |  | $\texttt{5}$ | In the second test case, the unknown integer $x = 1234$ and we have to make it equal to $n = 5$. |
    150 | $\texttt{digit}$ | $\texttt{1}$ | The answer to "digit" is "1". This means that $x$ turned into the sum of its digits $1 + 2 + 3 + 4 = 10$, and $x$ changes to $10$ after the command. |
    151 | $\texttt{div 2}$ | $\texttt{1}$ | The answer to "div 2" is "1". This means that the division command was successful as $y = 2$ is a divisor of $x = 10$, and $x$ changes to $\frac{x}{y} = \frac{10}{2} = 5$ after the command. |
    152 | $\texttt{!}$ | $\texttt{1}$ | The answer to "!" is "1". This means you have determined that $x$ equals $n$. |
    153 
    154 Note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.