Solution-CF2109C3

· · 题解

有大神拿这题做儿童节游园会小游戏，所以写篇题解。

C2 题解。

既然 C2 要求是 4 次，那么我们可以先尝试 3 次操作，再尝试 2 次操作（1 次操作显然不可行）。

考虑 C2 有哪次操作可以不用，显然最后 1 次操作优化不掉，那就只能优化前 3 次操作，我们希望第 1 次操作乘上某个数后，只用 1 次 digit 就可以得到一个确定的数。

我们乘法最大可以乘 10^9，不妨尝试一下 9 的倍数，发现没有结论。然后尝试一下 9 个 9 组成的数，即 10^9-1。可以发现：

\begin{aligned}(10^9-1)x&=10^9x-x\\&=10^9(x-1)+10^9-x\\&=[10^9(x-1)]+[(10^9-1)-(x-1)]\end{aligned}

令 x-1=\overline{a_1\cdots a_9}，那么 (10^9-1)x=\overline{a_1\cdots a_9(9-a_1)\cdots(9-a_9)}。

于是 S((10^9-1)x)=a_1+(9-a_1)+\cdots+a_9+(9-a_9)=9\times9=81。

于是现在我们找到了 3 次操作的做法。对于 n=81 可以略去最后 1 次操作，只需要 2 次操作。那么有没有什么其他的 n 是只需要 2 次操作就可以得到的呢？

假设存在 a\ne10^9-1 使得 S(ax)=n_0，取 x=10^9-1，由上面的结论可以知道 S(ax)=81。而我们再取 x=1，S(ax)=S(a)，只有取 a=10^9-1 才能使 S(a)=81。于是我们证明了只有 n=81 是只需要 2 次操作就可以得到的。

最终答案：

if(n==81){
    cout<<"mul 999999999\n";
    cout<<"digit\n";
}
else{
    cout<<"mul 999999999\n";
    cout<<"digit\n";
    cout<<"add"<<n-81<<"\n";
}