A13708 | Deleting Numbers
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
This is an interactive problem.
There is an unknown integer $x$ ( $1\le x\le n$ ). You want to find $x$ .
At first, you have a set of integers $\{1, 2, \ldots, n\}$ . You can perform the following operations no more than $10000$ times:
- A $a$ : find how many numbers are multiples of $a$ in the current set.
- B $a$ : find how many numbers are multiples of $a$ in this set, and then delete all multiples of $a$ , but $x$ will never be deleted (even if it is a multiple of $a$ ). In this operation, $a$ must be greater than $1$ .
- C $a$ : it means that you know that $x=a$ . This operation can be only performed once.
Remember that in the operation of type B $a>1$ must hold.
Write a program, that will find the value of $x$ .
There is an unknown integer $x$ ( $1\le x\le n$ ). You want to find $x$ .
At first, you have a set of integers $\{1, 2, \ldots, n\}$ . You can perform the following operations no more than $10000$ times:
- A $a$ : find how many numbers are multiples of $a$ in the current set.
- B $a$ : find how many numbers are multiples of $a$ in this set, and then delete all multiples of $a$ , but $x$ will never be deleted (even if it is a multiple of $a$ ). In this operation, $a$ must be greater than $1$ .
- C $a$ : it means that you know that $x=a$ . This operation can be only performed once.
Remember that in the operation of type B $a>1$ must hold.
Write a program, that will find the value of $x$ .
输入格式
The first line contains one integer $n$ ( $1\le n\le 10^5$ ). The remaining parts of the input will be given throughout the interaction process.
输出格式
In each round, your program needs to print a line containing one uppercase letter A, B or C and an integer $a$ ( $1\le a\le n$ for operations A and C, $2\le a\le n$ for operation B). This line desribes operation you make.
If your operation has type C your program should terminate immediately.
Else your program should read one line containing a single integer, which is the answer to your operation.
After outputting each line, don't forget to flush the output. To do it use:
- fflush(stdout) in C/C++;
- System.out.flush() in Java;
- sys.stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages.
It is guaranteed, that the number $x$ is fixed and won't change during the interaction process.
Hacks:
To make a hack, use such input format:
The only line should contain two integers $n$ , $x$ ( $1 \leq x \leq n \leq 10^5$ ).
If your operation has type C your program should terminate immediately.
Else your program should read one line containing a single integer, which is the answer to your operation.
After outputting each line, don't forget to flush the output. To do it use:
- fflush(stdout) in C/C++;
- System.out.flush() in Java;
- sys.stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages.
It is guaranteed, that the number $x$ is fixed and won't change during the interaction process.
Hacks:
To make a hack, use such input format:
The only line should contain two integers $n$ , $x$ ( $1 \leq x \leq n \leq 10^5$ ).
输入输出样例
输入 #1
10 2 4 0
输出 #1
B 4 A 2 A 8 C 4
Note that to make the sample more clear, we added extra empty lines. You shouldn't print any extra empty lines during the interaction process.
In the first test $n=10$ and $x=4$ .
Initially the set is: $\{1,2,3,4,5,6,7,8,9,10\}$ .
In the first operation, you ask how many numbers are multiples of $4$ and delete them. The answer is $2$ because there are two numbers divisible by $4$ : $\{4,8\}$ . $8$ will be deleted but $4$ won't, because the number $x$ will never be deleted. Now the set is $\{1,2,3,4,5,6,7,9,10\}$ .
In the second operation, you ask how many numbers are multiples of $2$ . The answer is $4$ because there are four numbers divisible by $2$ : $\{2,4,6,10\}$ .
In the third operation, you ask how many numbers are multiples of $8$ . The answer is $0$ because there isn't any number divisible by $8$ in the current set.
In the fourth operation, you know that $x=4$ , which is the right answer.
In the first test $n=10$ and $x=4$ .
Initially the set is: $\{1,2,3,4,5,6,7,8,9,10\}$ .
In the first operation, you ask how many numbers are multiples of $4$ and delete them. The answer is $2$ because there are two numbers divisible by $4$ : $\{4,8\}$ . $8$ will be deleted but $4$ won't, because the number $x$ will never be deleted. Now the set is $\{1,2,3,4,5,6,7,9,10\}$ .
In the second operation, you ask how many numbers are multiples of $2$ . The answer is $4$ because there are four numbers divisible by $2$ : $\{2,4,6,10\}$ .
In the third operation, you ask how many numbers are multiples of $8$ . The answer is $0$ because there isn't any number divisible by $8$ in the current set.
In the fourth operation, you know that $x=4$ , which is the right answer.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted