专栏文章

CF2109C2 Hacking Numbers (Medium Version) 解题报告

__mi_ka_
CF2109C2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8ysaa
此快照首次捕获于
2025/12/03 08:06
3 个月前
此快照最后确认于
2025/12/03 08:06
3 个月前
查看原文
题目传送门

题目大意

交互题。TT 组数据，每组给定一个整数 n(1≤n≤109)n(1\le n\le 10^9)，评测机中有一个隐藏的整数 x(1≤x≤109)x(1\le x\le10^9)。你可以对这个隐藏的 xx 做出以下四种操作若干次（这里 C2 这道题要求最多 44 次）将隐藏的 xx 变成 nn。
  1. add y 表示将 xx 增加 y(−1018≤y≤1018)y(-10^{18}\le y\le 10^{18})；
  2. mul y 表示将 xx 乘上 y(1≤y≤1018)y(1\le y\le 10^{18})；
  3. div y 表示将 xx 除以 y(1≤y≤1018)y(1\le y\le 10^{18})；
  4. digit 表示将 xx 的十进制各位数字相加，赋值给 xx；
在以上的四种操作中，如果假设 xx 操作后得到的数为 resres，那么当且仅当 1≤res≤10181\le res\le 10^{18} 且 resres 为整数时此次操作有效，交互机会返回 11，否则这次操作无效，xx 不做改变，交互机返回 00。
在确定 x=nx=n 时给交互机一个指令 ! 结束这组数据，这时交互机会返回一个值 11（正确）或者 −1-1（错误）。

解题思路

一种思路为可以将 xx 经过若干次操作后使得 xx 变成我们可以确定的数，然后再经过最多一次操作使得 xx 变为 nn。这里我们需要保留最后一次将 xx 由我们已知的数字变为 nn 的过程，那么题意就变成了：最多 33 次操作使得 xx 变成一个确定的数。
如何去选取这个确定的数呢？在 C1 中我们选取数字 11 作为这个数字，但是缩小范围的过程过于繁琐，可不可以将这个数缩小成一个更大一点的确定的数呢？这里就需要用到我们小学数学中学到的一个结论：任何能被 99 整除的数，其十进制各位数字之和为 99 的倍数。该定理过于简单，这里不做证明。这里我们对 xx 先乘一个 99，在去观察是否能够通过两次操作使得 xx 变成 99。即：
  1. mul 9 得到 1≤x≤109→9≤x≤9×1091\le x\le 10^9\to 9\le x\le 9\times10^9；
  2. digit 得到 9≤x≤9×109→9≤x≤819\le x\le 9\times 10^9\to 9\le x\le 81 且由结论得 9∣x9\mid x。至于这里为什么还是 8181，我们很容易想到这里能取到的最大的数字 89999999998999999999，它的各位之和是 8989，所以可以写出 1≤x≤891\le x\le 89，但是由于 9∣x9\mid x，自然引出结论 9≤x≤819\le x\le 81；
  3. 考虑 99 到 8181 之间的所有 99 的倍数，它的各位之和为 99。于是再进行一次 digit 操作得到 9≤x≤81→x=99\le x\le 81\to x=9。
最后进行一次操作 add n-9 即可得到数字 nn。这里还是有一个细节就是当 n=9n=9 时这一步操作不合法，所以需要特判一下。
单次时间复杂度 O(1)O(1)。
不要忘记每次输出后清空缓存区哦。

AC Code

这里只放主函数
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...