CF2109C1 Hacking Numbers (Easy Version) 解题报告

· · 题解

题目传送门

题目大意

交互题。T 组数据，每组给定一个整数 n(1\le n\le 10^9)，评测机中有一个隐藏的整数 x(1\le x\le10^9)。你可以对这个隐藏的 x 做出以下四种操作若干次（这里 C1 这道题要求最多 7 次）将隐藏的 x 变成 n。

  1. add y 表示将 x 增加 y(-10^{18}\le y\le 10^{18})；
  2. mul y 表示将 x 乘上 y(1\le y\le 10^{18})；
  3. div y 表示将 x 除以 y(1\le y\le 10^{18})；
  4. digit 表示将 x 的十进制各位数字相加，赋值给 x；

在以上的四种操作中，如果假设 x 操作后得到的数为 res，那么当且仅当 1\le res\le 10^{18} 且 res 为整数时此次操作有效，交互机会返回 1，否则这次操作无效，x 不做改变，交互机返回 0。

在确定 x=n 时给交互机一个指令 ! 结束这组数据，这时交互机会返回一个值 1（正确）或者 -1（错误）。

解题思路

一种思路为可以将 x 经过若干次操作后使得 x 变成我们可以确定的数，然后再经过最多一次操作使得 x 变为 n。这里我们需要保留最后一次将 x 由我们已知的数字变为 n 的过程，那么题意就变成了：最多 6 次操作使得 x 变成一个确定的数。

那么如何去选取这个确定的数呢？最容易想到的这个确定的数就是 1。将 x(x\ge 1) 变为 1，显然就是要将 x 这个数缩小。如何进行缩小？这就锁定了 digit、add 和 div 三种操作。由于 div 操作必须是整除这次操作才有效，所以我们这里不考虑 div 操作。

  1. 第一次缩小：显而易见 digit 操作可以将这个范围缩小到更小，于是：1\le x\le 10^9\to1\le x\le81(x=10^9-1\ 时取到\ 81)；
  2. 第二次缩小：这里再用一次 digit 操作可以将范围继续缩小，于是：1\le x\le 81\to1\le x\le16(x=79\ 时取到\ 16)；
  3. 第三次缩小：注意这里如果再用一次 digit 操作最多最多将 x 缩小到 1\le x\le 9，而运用 add 操作每次可以将范围折半，即 add y 这里 y 取 \left \lceil \frac{x}{2} \right \rceil ，这样我们就可以用 add -8 操作得到：1\le x\le 16\to1\le x\le8；
  4. 同理可得第四次缩小 add -4 得到 1\le x\le 8\to1\le x\le4；
  5. 第五次缩小 add -2得到1\le x\le 4\to1\le x\le2；
  6. 第六次缩小 add -1得到1\le x\le 2\to x=1；

六次结束，这里 x 已经是 1，可以最多一次操作得到 n，这里有个细节：你可以进行 mul n 和 add n-1 两种操作得到 n，但是如果用了后者，你会得到 TLE 的好成绩，原因是当 n=1 时，你给出了不合法的操作 add 0，所以避免特判，我选择了前者。

单次时间复杂度 O(1)。

不要忘记每次输出后清空缓存区哦。

AC Code

这里只放主函数。

signed main()
{
    int T=re();
    while(T--)
    {
        int n=re();
        int ci=2;
        while(ci--)
        {
            puts("digit");
            cout.flush();
            int op=re();
        }
        puts("add -8");
        cout.flush();
        int op=re();
        puts("add -4");
        cout.flush();
        op=re();
        puts("add -2");
        cout.flush();
        op=re();
        puts("add -1");
        cout.flush();
        op=re();
        printf("mul %d\n",n);
        cout.flush();
        op=re();
        puts("!");
        cout.flush();
        op=re();
    }
    return 0;
}