2109C3. Hacking Numbers (Hard Version)（借鉴原题解）

consructive algorithms, interactive, math, number theory, 2600,

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

This is the hard version of the problem. In this version, the limit of commands you can send is described in the statement. 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"

Let 𝑓(𝑛) be the minimum integer such that there is a sequence of 𝑓(𝑛) commands that transforms 𝑥 into 𝑛 for all 𝑥(1≤𝑥≤109). You do not know the value of 𝑥 in advance. Find 𝑓(𝑛) such that, no matter what 𝑥 is, you can always transform it into 𝑛 using at most 𝑓(𝑛)commands.

Your task is to change 𝑥 into 𝑛 using at most 𝑓(𝑛) 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 commands.

If your program makes more than 𝑓(𝑛) commands (𝑓(𝑛) is described above) 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.

本关考验你的突发奇想能力！

提示1：

Medium Version的另一种解法是

txt

digit
mul 99
digit
add n-18

试说明这个方法的原理。

提示2：

$f (n)$ 几乎是一个常值函数。

提示3：

数据范围并非一无所用！

解析： 在小学的时候我们就学过两位数乘以 $99$ 的简便算法，先写这个两位数减 $1$ ，再接着后面写上 $100$ 减去这个两位数，这样做的原理应该无需多言了。那么，如果我们来考察这个乘积的digit值呢？我们发现这个四位数 $\overset{―}{a b c d}$ 满足 $\overset{―}{a b} + \overset{―}{c d} = 99$ ，并且由于没有进位，所以 $a + b + c + d \equiv 18$ 。也就是说，对于两位数，我们只用乘以 $99$ 再取digit就能把它变成 $18$ 。也就是说，对于两位数，我们只用乘以 $99$ 再取digit就能把它变成 $18$ 。同理地，乘的这个数不止可以是 $99$ ，对于三位数，我们只用乘以 $999$ 再取digit就能把它变成 $27$ ；对于四位数，我们只用乘以 $9999$ 再取digit就能把它变成 $36 \dots$ 对于 $n$ 位数，我们只用乘以 $10^{n} - 1$ 再取digit就能把它变成 $9 n$ 。Wait！这个题不是保证了 $x$ 是一个 $9$ 位数吗？那我们只用乘以 $999999999$ 就可以了！况且题目要求乘以后的结果在 $1 ∽ 10^{18}$ 之间，恰好满足要求！所以我们的做法就呼之欲出了。

第一步：为 $x \to 999999999 x$
第二步：为 $x \to S (x)$ ，此时一定得到 $81$
第三步：（如果 $x \neq 81$ ）加上 $n - 81$ 即可

代码：

python

for _ in range(int(input())):
    n = int(input())
    print("mul 999999999")
    input()
    print("digit")
    input()
    if n != 81:
        print(f"add {n-81}")
        input()
    print("!")
    input()

2109C3. Hacking Numbers (Hard Version)（借鉴原题解） ​

2109C3. Hacking Numbers (Hard Version)（借鉴原题解）