CF2109C2 Hacking Numbers (Medium Version) 解题报告

· · 题解

题目传送门

题目大意

交互题。T 组数据，每组给定一个整数 n(1\le n\le 10^9)，评测机中有一个隐藏的整数 x(1\le x\le10^9)。你可以对这个隐藏的 x 做出以下四种操作若干次（这里 C2 这道题要求最多 4 次）将隐藏的 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 的过程，那么题意就变成了：最多 3 次操作使得 x 变成一个确定的数。

如何去选取这个确定的数呢？在 C1 中我们选取数字 1 作为这个数字，但是缩小范围的过程过于繁琐，可不可以将这个数缩小成一个更大一点的确定的数呢？这里就需要用到我们小学数学中学到的一个结论：任何能被 9 整除的数，其十进制各位数字之和为 9 的倍数。该定理过于简单，这里不做证明。这里我们对 x 先乘一个 9，在去观察是否能够通过两次操作使得 x 变成 9。即：

  1. mul 9 得到 1\le x\le 10^9\to 9\le x\le 9\times10^9；
  2. digit 得到 9\le x\le 9\times 10^9\to 9\le x\le 81 且由结论得 9\mid x。至于这里为什么还是 81，我们很容易想到这里能取到的最大的数字 8999999999，它的各位之和是 89，所以可以写出 1\le x\le 89，但是由于 9\mid x，自然引出结论 9\le x\le 81；
  3. 考虑 9 到 81 之间的所有 9 的倍数，它的各位之和为 9。于是再进行一次 digit 操作得到 9\le x\le 81\to x=9。

最后进行一次操作 add n-9 即可得到数字 n。这里还是有一个细节就是当 n=9 时这一步操作不合法，所以需要特判一下。

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

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

AC Code

这里只放主函数

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