← 返回题目列表

Codeforces · 1406/E

E. 删除号码

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

这是一个交互问题。

有一个未知整数 $$$x$$$ ($$$1\le x\le n$$$)。您想要找到 $$$x$$$。

首先,你有一组整数 $$$\{1, 2, \ldots, n\}$$$。您可以执行以下操作不超过 $$$10000$$$ 次:

- A $$$a$$$:查找当前集合中有多少个数字是 $$$a$$$ 的倍数。
- B $$$a$$$:找出这个集合中有多少个数字是$$$a$$$的倍数,然后删除$$$a$$$的所有倍数,但$$$x$$$永远不会被删除(即使它是$$$a$$$的倍数)。在此操作中,$$$a$$$ 必须大于$$$1$$$。
- C $$$a$$$:这意味着你知道$$$x=a$$$。该操作只能执行一次。

请记住,在类型 B 的运算中 $$$a>1$$$ 必须成立。

编写一个程序,查找 $$$x$$$ 的值。

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$)。输入的其余部分将在整个交互过程中给出。

互动

在每一轮中,你的程序需要打印一行包含一个大写字母 A、B 或 C 和一个整数 $$$a$$$ ($$$1\le a\le n$$$ 对于操作 A 和 C,$$$2\le a\le n$$$ 对于操作 B)。这一行描述了您所做的操作。

如果您的操作具有类型 C,您的程序应立即终止。

否则你的程序应该读取包含单个整数的一行,这是你的操作的答案。

输出每一行后,不要忘记刷新输出。为此,请使用:

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

保证$$$x$$$这个数字是固定的,在交互过程中不会改变。

黑客:

要进行破解,请使用以下输入格式:

唯一的一行应包含两个整数 $$$n$$$、$$$x$$$ ($$$1 \leq x \leq n \leq 10^5$$$)。

示例

输入 #1

10

2

4

0

输出 #1

B 4

A 2

A 8

C 4

注意

请注意,为了使示例更加清晰,我们添加了额外的空行。在交互过程中不应打印任何额外的空行。

在第一个测试中 $$$n=10$$$ 和 $$$x=4$$$。

最初的集合是:$$$\{1,2,3,4,5,6,7,8,9,10\}$$$。

在第一个操作中,询问有多少个数字是 $$$4$$$ 的倍数并将其删除。答案是$$$2$$$,因为有两个数字可以被$$$4$$$整除:$$$\{4,8\}$$$。 $$$8$$$ 将被删除,但 $$$4$$$ 不会,因为数字 $$$x$$$ 永远不会被删除。现在集合是$$$\{1,2,3,4,5,6,7,9,10\}$$$。

在第二个操作中,你询问有多少个数字是 $$$2$$$ 的倍数。答案是$$$4$$$,因为有四个数字可以被$$$2$$$整除:$$$\{2,4,6,10\}$$$。

在第三个运算中,你询问有多少个数字是 $$$8$$$ 的倍数。答案是$$$0$$$,因为当前集合中没有任何数字可以被$$$8$$$整除。

在第四次运算中,您知道$$$x=4$$$,这是正确答案。