CF2109C1 Hacking Numbers (Easy Version) 解题报告

题目大意

交互题。

T

组数据，每组给定一个整数

n(1\le n\le 10^9)

，评测机中有一个隐藏的整数

x(1\le x\le10^9)

。你可以对这个隐藏的

x

做出以下四种操作若干次（这里 C1 这道题要求最多 $7$ 次）将隐藏的

x

变成

n

。

add y 表示将 $x$ 增加 $y(-10^{18}\le y\le 10^{18})$ ；
mul y 表示将 $x$ 乘上 $y(1\le y\le 10^{18})$ ；
div y 表示将 $x$ 除以 $y(1\le y\le 10^{18})$ ；
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 操作。

第一次缩小：显而易见 digit 操作可以将这个范围缩小到更小，于是： $1\le x\le 10^9\to1\le x\le81(x=10^9-1\ 时取到\ 81)$ ；
第二次缩小：这里再用一次 digit 操作可以将范围继续缩小，于是： $1\le x\le 81\to1\le x\le16(x=79\ 时取到\ 16)$ ；
第三次缩小：注意这里如果再用一次 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$ ；
同理可得第四次缩小 add -4 得到 $1\le x\le 8\to1\le x\le4$ ；
第五次缩小 add -2得到 $1\le x\le 4\to1\le x\le2$ ；
第六次缩小 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

这里只放主函数。

CPP

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;
}

CF2109C1 Hacking Numbers (Easy Version) 解题报告

文章操作

题目大意

解题思路

AC Code

相关推荐

评论

CF2109C1 Hacking Numbers (Easy Version) 解题报告