← 返回题目列表

Codeforces · 1780/D

D. 猜猜游戏

中文机器翻译题面 查看原题

这是一个交互问题。

基拉有一个隐藏的正整数$$$n$$$,隼人需要猜测它。

最初,Kira 给 Hayato 的值 $$$\mathrm{cnt}$$$ — $$$n$$$ 的二进制表示法中的单位位数。为了猜测 $$$n$$$,Hayato 只能执行一种操作:选择一个整数 $$$x$$$ 并从 $$$n$$$ 中减去它。请注意,每次操作后,数字 $$$n$$$ 都会发生变化。基拉不喜欢糟糕的请求,所以如果隼人试图减去大于 $$$n$$$ 的数字 $$$x$$$,他就会输给基拉。每次操作后,Kira 都会向 Hayato 提供更新值 $$$\mathrm{cnt}$$$ — $$$n$$$ 更新值的二进制表示法中的单位位数。

Kira 没有太多耐心,所以 Hayato 必须在不超过 $$$30$$$ 操作后猜测 $$$n$$$ 的原始值。

由于隼人正在上小学,他请求你的帮助。编写一个程序来猜测数字$$$n$$$。 Kira是一个诚实的人,所以他在所有操作之前选择初始数字$$$n$$$并且之后不改变它。

输入

输入数据包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含数字 $$$\mathrm{cnt}$$$ — 二进制表示法 $$$n$$$ 中单位位数的初始数量。

隐藏整数 $$$n$$$ 满足以下约束:$$$1 \le n \le 10^9$$$。

互动

要猜测$$$n$$$,您最多可以执行$$$30$$$次操作。为此,请使用以下格式打印一行:“- x”($$$1 \le x \le 10^9$$$)。

执行此操作后,$$$x$$$ 会从 $$$n$$$ 中减去,因此 $$$n$$$ 会发生变化。如果数字 $$$x$$$ 大于 $$$n$$$ 的当前值,则该请求被视为无效。

运算后读取一行包含单个非负整数 $$$\mathrm{cnt}$$$ — 运算后当前 $$$n$$$ 的二进制单位位数。

当您知道 $$$n$$$ 的初始值时,按以下格式打印一行:“! n” ($$$1 \le n \le 10^9$$$)。

之后,继续进行下一个测试用例,如果没有则终止程序。

如果你的程序对一个测试用例执行了超过$$$30$$$操作,减去了一个大于$$$n$$$的数字$$$x$$$,或者提出了一个不正确的请求,那么对请求的响应将为-1,在收到这样的响应后,你的程序必须立即退出以接收错误答案判决。否则,您可以获得任何其他判决。

打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要进行破解,请使用以下格式。

第一行应包含单个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$)。

每个测试用例应在单独的行上包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^9$$$)。

示例

输入 #1

3

1

0

1

1

0

2

1

0

输出 #1

- 1

! 1

- 1

- 1

! 2

- 2

- 1

! 3

注意

例如,$$$6$$$中的单位位数为$$$2$$$,因为$$$6$$$的二进制表示为$$$110$$$。对于$$$13$$$,单位位数为$$$3$$$,因为$$$13_{10} = 1101_2$$$。

在第一个测试用例中,$$$n = 1$$$,因此输入是数字$$$1$$$。 $$$n$$$减一后变为0,因此其中的单位位数为$$$0$$$。

在第三个测试用例中,$$$n = 3$$$,其二进制表示形式为 $$$3_{10} = 11_2$$$,因此输入是 1 的数量,即 $$$2$$$。减去$$$2$$$后,$$$n = 1$$$,因此单位位数现在为$$$1$$$。 $$$n$$$ 减一后,它就等于零。

请注意,输入和输出示例中的空行是为了清楚起见而显示的,并且在实际交互中不存在。