310083: CF1780D. Bit Guessing Game
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Bit Guessing Game
题意翻译
## 题目描述 这是一道交互题。 Kira 和 Hayato 正在玩一种猜数游戏，Kira 想，Hayato 猜。 对于每一轮游戏，设 Kira 想的数为 $n$。初始时，Kira 会给出 $cnt$，表示 $n$ 的二进制中 $1$ 的个数。Hayato 只能进行以下两种操作： 1. `- x`：修改操作。Kira 会将 $n$ 减去 $x$（注意此处 $n$ 会被修改），并给出此时的 $cnt$。特别地，若 $x > n$，则 Kira 直接获胜。 2. `! x`：查询操作。Kira 会将 $x$ 与最初的 $n$ 对比，若二者相同则 Hayato 获胜，反之 Kira 获胜，这轮游戏立即结束。 他们一共会进行 $t$ 轮游戏，你需要帮助 Hayato 在每一轮中获胜。同时，Kira 并不是一个很有耐心的人，因此你进行操作 1 的次数不能超过 $30$。 注意样例中的空行只是为了显示更清晰，不会出现在实际评测中。 ## 输入格式 第一行包含一个整数 $t(1 \le t \le 500)$，表示有 $t$ 组测试用例。 对于每组测试用例，首行均为一个整数 $cnt$，表示 $n$ 的二进制中 $1$ 的个数。 保证 $1 \le n \le 10^9$。 ## 输出格式 对于每个操作 1，输出单独的一行 `- x`；相应地，对于每个操作 2，输出单独的一行 `! n`。 每个操作 1 完成后，交互库会输出一行一个整数 $cnt$，表示修改后的 $n$ 的二进制中 $1$ 的个数。 再次强调，每一轮 Hayato 进行操作 1 的次数不能超过 $30$。 确定初始时 $n$ 的值后，可进行操作 2 验证答案。 注意：每次输出任意操作后需要刷新输出。这里给出部分语言刷新输出的代码： | 语言 | 代码 | | :----: | :--------------------------------: | | C++ | `fflush(stdout)` 或 `cout.flush()` | | Java | `System.out.flush()` | | Pascal | `flush(output)` | | Python | `stdout.flush()` |题目描述
This is an interactive problem. Kira has a hidden positive integer $ n $ , and Hayato needs to guess it. Initially, Kira gives Hayato the value $ \mathrm{cnt} $ — the number of unit bits in the binary notation of $ n $ . To guess $ n $ , Hayato can only do operations of one kind: choose an integer $ x $ and subtract it from $ n $ . Note that after each operation, the number $ n $ changes. Kira doesn't like bad requests, so if Hayato tries to subtract a number $ x $ greater than $ n $ , he will lose to Kira. After each operation, Kira gives Hayato the updated value $ \mathrm{cnt} $ — the number of unit bits in the binary notation of the updated value of $ n $ . Kira doesn't have much patience, so Hayato must guess the original value of $ n $ after no more than $ 30 $ operations. Since Hayato is in elementary school, he asks for your help. Write a program that guesses the number $ n $ . Kira is an honest person, so he chooses the initial number $ n $ before all operations and does not change it afterward.输入输出格式
输入格式
The input data contains several test cases. The first line contains one integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains the number $ \mathrm{cnt} $ — the initial number of unit bits in the binary notation $ n $ . The hidden integer $ n $ satisfies the following constraint: $ 1 \le n \le 10^9 $ .
输出格式
To guess $ n $ , you can perform the operation at most $ 30 $ times. To do that, print a line with the following format: "- x" ( $ 1 \le x \le 10^9 $ ). After this operation, the number $ x $ is subtracted from $ n $ , and therefore $ n $ is changed. If the number $ x $ is greater than the current value of $ n $ , then the request is considered invalid. After the operation read a line containing a single non-negative integer $ \mathrm{cnt} $ — the number of unit bits in the binary notation of the current $ n $ after the operation. When you know the initial value of $ n $ , print one line in the following format: "! n" ( $ 1 \le n \le 10^9 $ ). After that, move on to the next test case, or terminate the program if there are none. If your program performs more than $ 30 $ operations for one test case, subtracts a number $ x $ greater than $ n $ , or makes an incorrect request, then response to the request will be -1, after receiving such response, your program must exit immediately to receive the Wrong Answer verdict. Otherwise, you can get any other verdict. After printing a query or the answer, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks To make a hack, use the following format. The first line should contain a single integer $ t $ ( $ 1 \leq t \leq 500 $ ). Each test case should contain one integer $ n $ ( $ 1 \leq n \leq 10^9 $ ) on a separate line.
输入输出样例
输入样例 #1
3
1
0
1
1
0
2
1
0输出样例 #1
- 1
! 1
- 1
- 1
! 2
- 2
- 1
! 3说明
For example, the number of unit bits in number $ 6 $ is $ 2 $ , because binary notation of $ 6 $ is $ 110 $ . For $ 13 $ the number of unit bits is $ 3 $ , because $ 13_{10} = 1101_2 $ . In the first test case, $ n = 1 $ , so the input is the number $ 1 $ . After subtracting one from $ n $ , it becomes zero, so the number of unit bits in it is $ 0 $ . In the third test case, $ n = 3 $ , which in binary representation looks like $ 3_{10} = 11_2 $ , so the input is the number of ones, that is $ 2 $ . After subtracting $ 2 $ , $ n = 1 $ , so the number of unit bits is now $ 1 $ . After subtracting one from $ n $ , it becomes equal to zero. Note that the blank lines in the input and output examples are shown for clarity and are not present in the actual interaction.Input
题意翻译
## 题目描述 这是一道交互题。 Kira 和 Hayato 正在玩一种猜数游戏，Kira 想，Hayato 猜。 对于每一轮游戏，设 Kira 想的数为 $n$。初始时，Kira 会给出 $cnt$，表示 $n$ 的二进制中 $1$ 的个数。Hayato 只能进行以下两种操作： 1. `- x`：修改操作。Kira 会将 $n$ 减去 $x$（注意此处 $n$ 会被修改），并给出此时的 $cnt$。特别地，若 $x > n$，则 Kira 直接获胜。 2. `! x`：查询操作。Kira 会将 $x$ 与最初的 $n$ 对比，若二者相同则 Hayato 获胜，反之 Kira 获胜，这轮游戏立即结束。 他们一共会进行 $t$ 轮游戏，你需要帮助 Hayato 在每一轮中获胜。同时，Kira 并不是一个很有耐心的人，因此你进行操作 1 的次数不能超过 $30$。 注意样例中的空行只是为了显示更清晰，不会出现在实际评测中。 ## 输入格式 第一行包含一个整数 $t(1 \le t \le 500)$，表示有 $t$ 组测试用例。 对于每组测试用例，首行均为一个整数 $cnt$，表示 $n$ 的二进制中 $1$ 的个数。 保证 $1 \le n \le 10^9$。 ## 输出格式 对于每个操作 1，输出单独的一行 `- x`；相应地，对于每个操作 2，输出单独的一行 `! n`。 每个操作 1 完成后，交互库会输出一行一个整数 $cnt$，表示修改后的 $n$ 的二进制中 $1$ 的个数。 再次强调，每一轮 Hayato 进行操作 1 的次数不能超过 $30$。 确定初始时 $n$ 的值后，可进行操作 2 验证答案。 注意：每次输出任意操作后需要刷新输出。这里给出部分语言刷新输出的代码： | 语言 | 代码 | | :----: | :--------------------------------: | | C++ | `fflush(stdout)` 或 `cout.flush()` | | Java | `System.out.flush()` | | Pascal | `flush(output)` | | Python | `stdout.flush()` |Output
**题目大意：**
这是一个交互式问题。
Kira 有一个隐藏的正整数 $ n $，而 Hayato 需要猜测它。
最初，Kira 给 Hayato 的值 $ cnt $ 是 $ n $ 的二进制表示中 1 的数量。为了猜测 $ n $，Hayato 只能进行一种操作：选择一个整数 $ x $ 并从 $ n $ 中减去它。注意，每次操作后，数字 $ n $ 会改变。如果 Hayato 尝试减去一个大于 $ n $ 的数字 $ x $，他将输给 Kira。每次操作后，Kira 会给 Hayato 更新的值 $ cnt $，即更新后的 $ n $ 的二进制表示中 1 的数量。
Kira 没有多少耐心，所以 Hayato 必须在不超过 30 次操作后猜测出 $ n $ 的原始值。
由于 Hayato 才上小学，他请求你的帮助。写一个程序来猜测数字 $ n $。Kira 是一个诚实的人，所以他在所有操作之前选择初始数字 $ n $，并且在之后不会改变它。
**输入输出数据格式：**
**输入格式：**
输入数据包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 500 $）——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含数字 $ cnt $ —— $ n $ 的二进制表示中的初始 1 的数量。
隐藏的整数 $ n $ 满足以下约束：$ 1 \le n \le 10^9 $。
**输出格式：**
为了猜测 $ n $，你可以最多执行 30 次操作。为此，打印以下格式的行："- x"（$ 1 \le x \le 10^9 $）。
执行此操作后，从 $ n $ 中减去数字 $ x $，因此 $ n $ 会改变。如果数字 $ x $ 大于当前的 $ n $ 值，则该请求被认为是无效的。
在操作后读取一行，包含一个非负整数 $ cnt $ —— 操作后当前 $ n $ 的二进制表示中的 1 的数量。
当你知道 $ n $ 的初始值时，打印以下格式的行： "! n"（$ 1 \le n \le 10^9 $）。
然后，进行下一个测试用例，如果没有则终止程序。
如果你的程序对一个测试用例执行超过 30 次操作，减去一个大于 $ n $ 的数字 $ x $，或者提出错误请求，那么对请求的响应将是 -1，在收到这样的响应后，你的程序必须立即退出以获得错误的答案。否则，你可以得到任何其他判断。
在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，请使用：
- 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`;
- 在 Java 中使用 `System.out.flush()`;
- 在 Pascal 中使用 `flush(output)`;
- 在 Python 中使用 `stdout.flush()`;
- 其他语言的文档中查看如何操作。
**样例解释：**
例如，数字 6 中的 1 的数量是 2，因为 6 的二进制表示是 110。对于 13，1 的数量是 3，因为 $ 13_{10} = 1101_2 $。
在第一个测试用例中，$ n = 1 $，所以输入是数字 1。从 $ n $ 中减去 1 后，它变成零，所以它中的 1 的数量是 0。
在第三个测试用例中，$ n = 3 $，在二进制中表示为 $ 3_{10} = 11_2 $，所以输入是 1 的数量，即 2。减去 2 后，$ n = 1 $，所以 1 的数量现在是 1。从 $ n $ 中减去 1 后，它变成零。
注意，输入和输出示例中的空白行是为了清晰显示而添加的，在实际交互中不会出现。**题目大意：** 这是一个交互式问题。 Kira 有一个隐藏的正整数 $ n $，而 Hayato 需要猜测它。 最初，Kira 给 Hayato 的值 $ cnt $ 是 $ n $ 的二进制表示中 1 的数量。为了猜测 $ n $，Hayato 只能进行一种操作：选择一个整数 $ x $ 并从 $ n $ 中减去它。注意，每次操作后，数字 $ n $ 会改变。如果 Hayato 尝试减去一个大于 $ n $ 的数字 $ x $，他将输给 Kira。每次操作后，Kira 会给 Hayato 更新的值 $ cnt $，即更新后的 $ n $ 的二进制表示中 1 的数量。 Kira 没有多少耐心，所以 Hayato 必须在不超过 30 次操作后猜测出 $ n $ 的原始值。 由于 Hayato 才上小学，他请求你的帮助。写一个程序来猜测数字 $ n $。Kira 是一个诚实的人，所以他在所有操作之前选择初始数字 $ n $，并且在之后不会改变它。 **输入输出数据格式：** **输入格式：** 输入数据包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 500 $）——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含数字 $ cnt $ —— $ n $ 的二进制表示中的初始 1 的数量。 隐藏的整数 $ n $ 满足以下约束：$ 1 \le n \le 10^9 $。 **输出格式：** 为了猜测 $ n $，你可以最多执行 30 次操作。为此，打印以下格式的行："- x"（$ 1 \le x \le 10^9 $）。 执行此操作后，从 $ n $ 中减去数字 $ x $，因此 $ n $ 会改变。如果数字 $ x $ 大于当前的 $ n $ 值，则该请求被认为是无效的。 在操作后读取一行，包含一个非负整数 $ cnt $ —— 操作后当前 $ n $ 的二进制表示中的 1 的数量。 当你知道 $ n $ 的初始值时，打印以下格式的行： "! n"（$ 1 \le n \le 10^9 $）。 然后，进行下一个测试用例，如果没有则终止程序。 如果你的程序对一个测试用例执行超过 30 次操作，减去一个大于 $ n $ 的数字 $ x $，或者提出错误请求，那么对请求的响应将是 -1，在收到这样的响应后，你的程序必须立即退出以获得错误的答案。否则，你可以得到任何其他判断。 在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，请使用： - 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`; - 在 Java 中使用 `System.out.flush()`; - 在 Pascal 中使用 `flush(output)`; - 在 Python 中使用 `stdout.flush()`; - 其他语言的文档中查看如何操作。 **样例解释：** 例如，数字 6 中的 1 的数量是 2，因为 6 的二进制表示是 110。对于 13，1 的数量是 3，因为 $ 13_{10} = 1101_2 $。 在第一个测试用例中，$ n = 1 $，所以输入是数字 1。从 $ n $ 中减去 1 后，它变成零，所以它中的 1 的数量是 0。 在第三个测试用例中，$ n = 3 $，在二进制中表示为 $ 3_{10} = 11_2 $，所以输入是 1 的数量，即 2。减去 2 后，$ n = 1 $，所以 1 的数量现在是 1。从 $ n $ 中减去 1 后，它变成零。 注意，输入和输出示例中的空白行是为了清晰显示而添加的，在实际交互中不会出现。
这是一个交互式问题。
Kira 有一个隐藏的正整数 $ n $，而 Hayato 需要猜测它。
最初，Kira 给 Hayato 的值 $ cnt $ 是 $ n $ 的二进制表示中 1 的数量。为了猜测 $ n $，Hayato 只能进行一种操作：选择一个整数 $ x $ 并从 $ n $ 中减去它。注意，每次操作后，数字 $ n $ 会改变。如果 Hayato 尝试减去一个大于 $ n $ 的数字 $ x $，他将输给 Kira。每次操作后，Kira 会给 Hayato 更新的值 $ cnt $，即更新后的 $ n $ 的二进制表示中 1 的数量。
Kira 没有多少耐心，所以 Hayato 必须在不超过 30 次操作后猜测出 $ n $ 的原始值。
由于 Hayato 才上小学，他请求你的帮助。写一个程序来猜测数字 $ n $。Kira 是一个诚实的人，所以他在所有操作之前选择初始数字 $ n $，并且在之后不会改变它。
**输入输出数据格式：**
**输入格式：**
输入数据包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 500 $）——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含数字 $ cnt $ —— $ n $ 的二进制表示中的初始 1 的数量。
隐藏的整数 $ n $ 满足以下约束：$ 1 \le n \le 10^9 $。
**输出格式：**
为了猜测 $ n $，你可以最多执行 30 次操作。为此，打印以下格式的行："- x"（$ 1 \le x \le 10^9 $）。
执行此操作后，从 $ n $ 中减去数字 $ x $，因此 $ n $ 会改变。如果数字 $ x $ 大于当前的 $ n $ 值，则该请求被认为是无效的。
在操作后读取一行，包含一个非负整数 $ cnt $ —— 操作后当前 $ n $ 的二进制表示中的 1 的数量。
当你知道 $ n $ 的初始值时，打印以下格式的行： "! n"（$ 1 \le n \le 10^9 $）。
然后，进行下一个测试用例，如果没有则终止程序。
如果你的程序对一个测试用例执行超过 30 次操作，减去一个大于 $ n $ 的数字 $ x $，或者提出错误请求，那么对请求的响应将是 -1，在收到这样的响应后，你的程序必须立即退出以获得错误的答案。否则，你可以得到任何其他判断。
在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，请使用：
- 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`;
- 在 Java 中使用 `System.out.flush()`;
- 在 Pascal 中使用 `flush(output)`;
- 在 Python 中使用 `stdout.flush()`;
- 其他语言的文档中查看如何操作。
**样例解释：**
例如，数字 6 中的 1 的数量是 2，因为 6 的二进制表示是 110。对于 13，1 的数量是 3，因为 $ 13_{10} = 1101_2 $。
在第一个测试用例中，$ n = 1 $，所以输入是数字 1。从 $ n $ 中减去 1 后，它变成零，所以它中的 1 的数量是 0。
在第三个测试用例中，$ n = 3 $，在二进制中表示为 $ 3_{10} = 11_2 $，所以输入是 1 的数量，即 2。减去 2 后，$ n = 1 $，所以 1 的数量现在是 1。从 $ n $ 中减去 1 后，它变成零。
注意，输入和输出示例中的空白行是为了清晰显示而添加的，在实际交互中不会出现。**题目大意：** 这是一个交互式问题。 Kira 有一个隐藏的正整数 $ n $，而 Hayato 需要猜测它。 最初，Kira 给 Hayato 的值 $ cnt $ 是 $ n $ 的二进制表示中 1 的数量。为了猜测 $ n $，Hayato 只能进行一种操作：选择一个整数 $ x $ 并从 $ n $ 中减去它。注意，每次操作后，数字 $ n $ 会改变。如果 Hayato 尝试减去一个大于 $ n $ 的数字 $ x $，他将输给 Kira。每次操作后，Kira 会给 Hayato 更新的值 $ cnt $，即更新后的 $ n $ 的二进制表示中 1 的数量。 Kira 没有多少耐心，所以 Hayato 必须在不超过 30 次操作后猜测出 $ n $ 的原始值。 由于 Hayato 才上小学，他请求你的帮助。写一个程序来猜测数字 $ n $。Kira 是一个诚实的人，所以他在所有操作之前选择初始数字 $ n $，并且在之后不会改变它。 **输入输出数据格式：** **输入格式：** 输入数据包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 500 $）——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含数字 $ cnt $ —— $ n $ 的二进制表示中的初始 1 的数量。 隐藏的整数 $ n $ 满足以下约束：$ 1 \le n \le 10^9 $。 **输出格式：** 为了猜测 $ n $，你可以最多执行 30 次操作。为此，打印以下格式的行："- x"（$ 1 \le x \le 10^9 $）。 执行此操作后，从 $ n $ 中减去数字 $ x $，因此 $ n $ 会改变。如果数字 $ x $ 大于当前的 $ n $ 值，则该请求被认为是无效的。 在操作后读取一行，包含一个非负整数 $ cnt $ —— 操作后当前 $ n $ 的二进制表示中的 1 的数量。 当你知道 $ n $ 的初始值时，打印以下格式的行： "! n"（$ 1 \le n \le 10^9 $）。 然后，进行下一个测试用例，如果没有则终止程序。 如果你的程序对一个测试用例执行超过 30 次操作，减去一个大于 $ n $ 的数字 $ x $，或者提出错误请求，那么对请求的响应将是 -1，在收到这样的响应后，你的程序必须立即退出以获得错误的答案。否则，你可以得到任何其他判断。 在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你将得到超时限制。为此，请使用： - 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`; - 在 Java 中使用 `System.out.flush()`; - 在 Pascal 中使用 `flush(output)`; - 在 Python 中使用 `stdout.flush()`; - 其他语言的文档中查看如何操作。 **样例解释：** 例如，数字 6 中的 1 的数量是 2，因为 6 的二进制表示是 110。对于 13，1 的数量是 3，因为 $ 13_{10} = 1101_2 $。 在第一个测试用例中，$ n = 1 $，所以输入是数字 1。从 $ n $ 中减去 1 后，它变成零，所以它中的 1 的数量是 0。 在第三个测试用例中，$ n = 3 $，在二进制中表示为 $ 3_{10} = 11_2 $，所以输入是 1 的数量，即 2。减去 2 后，$ n = 1 $，所以 1 的数量现在是 1。从 $ n $ 中减去 1 后，它变成零。 注意，输入和输出示例中的空白行是为了清晰显示而添加的，在实际交互中不会出现。