2109C1. Hacking Numbers (Easy Version)

bitmasks, constructive algorithms, interactive, math, number theory, 1500

https://codeforces.com/problemset/problem/2109/C1

This is the easy version of the problem. In this version, you can send at most *7* commands. You can make hacks only if all versions of the problem are solved.

This is an interactive problem.

Welcome, Duelists! In this interactive challenge, there is an unknown integer 𝑥 (1≤𝑥≤109). You must make it equal to a given integer in the input 𝑛. By harnessing the power of "Mathmech" monsters, you can send a command to do one of the following:

Command	Constraint	Result	Case	Update	Jury's response
"add 𝑦"	−1018≤𝑦≤1018	res=𝑥+𝑦	if 1≤res≤1018	𝑥←res	"1"
else	𝑥←𝑥	"0"
"mul 𝑦"	1≤𝑦≤1018	res=𝑥⋅𝑦	if 1≤res≤1018	𝑥←res	"1"
else	𝑥←𝑥	"0"
"div 𝑦"	1≤𝑦≤1018	res=𝑥/𝑦	if 𝑦 divides 𝑥	𝑥←res	"1"
else	𝑥←𝑥	"0"
"digit"	—	res=𝑆(𝑥)∗	—	𝑥←res	"1"

You have to make 𝑥 equal to 𝑛 using at most 7 commands.

∗𝑆(𝑛) is a function that returns the sum of all the individual digits of a non-negative integer 𝑛. For example, 𝑆(123)=1+2+3=6

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤5000). The description of the test cases follows.

The first and only line of each test case contains one integer 𝑛 (1≤𝑛≤109).

Interaction

The interaction for each test case begins by reading the integer 𝑛.

To send a command, output a line in the following format:

"add 𝑦" Add some integer 𝑦 (−1018≤𝑦≤1018) to 𝑥.
The jury will output "1" if 𝑥+𝑦 is within [1,1018] (successful), and "0" otherwise. If successful, update 𝑥←𝑥+𝑦.
"mul 𝑦" Multiply 𝑥 by a positive integer 𝑦 (1≤𝑦≤1018).
The jury will output "1" if 𝑥⋅𝑦 is within [1,1018] (successful), and "0" otherwise. If successful, update 𝑥←𝑥⋅𝑦.
"div 𝑦" Divide 𝑥 by a positive integer 𝑦 (1≤𝑦≤1018).
The jury will output "1" if 𝑦 is a divisor of 𝑥 (successful), and "0" otherwise. If successful, update 𝑥←𝑥𝑦.
"digit" Make 𝑥 equal to the sum of its digits.
The jury will always output "1" and update 𝑥←𝑆(𝑥).

Note that commands are case sensitive.

When you have determined that 𝑥 is equal to 𝑛, output a line in the following format:

"!" — where the jury will output a "1" if 𝑛 is equal to 𝑥, and "-1" otherwise.

Note that answering does not count toward your limit of 7 commands.

If your program makes more than 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.

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:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
sys.stdout.flush() in Python;
std::io::stdout().flush() in Rust;
see the documentation for other languages.

The interactor is non-adaptive. The unknown integer 𝑥 does not change during the interaction.

Hacks

To hack, use the following format.

The first line should contain a single integer 𝑡 (1≤𝑡≤5000) — the number of test cases.

The first line of each test case should contain two positive integers 𝑛 and 𝑥 (1≤𝑛,𝑥≤109) — denoting the unknown integer and the target value to which it should be made equal, respectively.

Example

input

output

add -10

add 1

mul 10

!

digit

div 2

!

Note

Solution	Jury	Explanation
	𝟸	There are 2 test cases.
	𝟷𝟶𝟶	In the first test case, the unknown integer 𝑥=9 and we have to make it equal to 𝑛=100.
𝚊𝚍𝚍 -𝟷𝟶	𝟶	The answer to "add -10" is "0". This means that the addition command was not successful as 𝑥+𝑦=9+(−10)≤0, and 𝑥 remains 9 after the command
𝚊𝚍𝚍 𝟷	𝟷	The answer to "add 1" is "1". This means that the addition command was successful as 𝑥+𝑦=9+1=10, and 𝑥 changes to 10 after the command.
𝚖𝚞𝚕 𝟷𝟶	𝟷	The answer to "mul 10" is "1". This means that the multiplication command was successful as 𝑥⋅𝑦=10⋅10=100, and 𝑥 changes to 100 after the command.
!	𝟷	The answer to "!" is "1". This means you have determined that 𝑥 equals 𝑛.
	𝟻	In the second test case, the unknown integer 𝑥=1234 and we have to make it equal to 𝑛=5.
𝚍𝚒𝚐𝚒𝚝	𝟷	The answer to "digit" is "1". This means that 𝑥 turned into the sum of its digits 1+2+3+4=10, and 𝑥changes to 10 after the command.
𝚍𝚒𝚟 𝟸	𝟷	The answer to "div 2" is "1". This means that the division command was successful as 𝑦=2 is a divisor of 𝑥=10, and 𝑥 changes to 𝑥𝑦=102=5 after the command.
!	𝟷	The answer to "!" is "1". This means you have determined that 𝑥 equals 𝑛.

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.

【尹显齐 2500011456 物理学院】

这一问主要是奠定基础。
想要将一个未知的数变成 $n$ ，能想到的方法只能是先将它变成一个你能确定的数 $x_{0}$ ，再加上 $n - x_{0}$ 。分析一下命令特点：第一个"add y"，如果我们知道未知数所在范围，可以将它的范围缩小到原来一半；第二个"mul y"，目前不知道干嘛，因为它只能增大原来的数；第三个"div y"，纯废物命令，我都不知道未知数能被哪些数整除，有啥用？第四个"digit"，在数很大时能快速缩小数。考虑到 digit 命令能快速缩小数，便有了如下方法：

第一步：为 $x \to S (x)$ ，由于 $1 \leq x \leq 10^{9}$ ，所以得到的数不超过 $81$
第二步：依旧是 $x \to S (x)$ ，由于 $1 \leq x \leq 81$ ，所以得到的数不超过 $16$
第三步：接下来再用digit就不好了，因为有个位数的存在。此时对半的减下去，效果最好。所以命令是 $x \to x - 8$ ，此时 $x$ 范围在 $[1, 8]$ 。同理有：
第四步：为 $x \to x - 4$ ，此时 $x$ 范围在 $[1, 4]$
第五步：为 $x \to x - 2$ ，此时 $x$ 范围在 $[1, 2]$
第六步：为 $x \to x - 1$ ，此时 $x$ 范围在 $[1, 1]$ 此时未知数 $x$ 已经确定地变成 $1$ 了，加上 $n - 1$ 即可。这样我们就在 $7$ 步内解决了这个问题。

代码：

python

for _ in range(int(input())):
    n = int(input())
    print("digit")
    input()
    print("digit")
    input()
    print("add -8")
    input()
    print("add -4")
    input()
    print("add -2")
    input()
    print("add -1")
    input()
    print(f"add {n-1}")
    input()
    print("!")
    input()

2109C1. Hacking Numbers (Easy Version) ​

2109C1. Hacking Numbers (Easy Version)