AT_arc233_a.Strange Subset Sum
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is an interactive problem (where your program interacts with the judge system via Standard Input and Output).
You are given a positive integer N.
For a set X of positive integers, a subset of X whose sum is N is called a special subset of X.
The judge system has a hidden set A that satisfies all of the following conditions, but you cannot directly know the values of the elements of A.
- ∣A∣=⌊2N⌋
- Every element of A is an integer between 1 and N−1, inclusive.
You may ask the judge system the following question at most ⌊43N⌋ times.
- Choose an integer a between 1 and N−1, inclusive, and ask whether a is contained in A.
Determine whether the hidden set A has a special subset, and if it does, find the minimum number of elements in a special subset.
Solve T test cases for each input.
这是一个交互式问题(你的程序需通过标准输入和输出与评测系统进行交互)。
你将得到一个正整数 N。
对于一个正整数集合 X,若其某个子集的元素之和等于 N,则该子集称为 X 的一个特殊子集。
评测系统内部隐藏了一个集合 A,它满足以下所有条件,但你无法直接得知 A 中各元素的具体取值:
- ∣A∣=⌊2N⌋
- A 中每个元素均为介于 1 和 N−1(含端点)之间的整数。
你最多可向评测系统提出 ⌊43N⌋ 次如下形式的询问:
- 选择一个介于 1 和 N−1(含端点)之间的整数 a,询问 a 是否属于 A。
请判断隐藏集合 A 是否存在特殊子集;若存在,请找出特殊子集中元素个数的最小值。
对每组输入,需解决 T 个测试用例。
说明/提示
Interaction
This is an interactive problem (where your program interacts with the judge system via Standard Input and Output).
First, receive the number of test cases T from Standard Input.
T
Then, T test cases follow. Each test case proceeds as follows.
Receive the integer N from Standard Input.
N
Then, you may ask at most ⌊43N⌋ questions. Print each question to Standard Output in the following format:
? a
Here, a must satisfy the following:
- 1≤a≤N−1
- a is an integer.
In response, Yes is given from Standard Input if a is contained in A, and No is given otherwise.
However, if a does not satisfy the conditions above, or if the number of questions exceeds ⌊43N⌋, -1 is returned.
If the judge returns -1, your program is already considered incorrect. In this case, terminate your program immediately.
Let S=−1 if A has no special subset; otherwise, let S be the minimum number of elements in a special subset.
Once you have found S, print it to Standard Output in the following format.
! S
Then, proceed to the next test case if one exists. After processing the last test case, terminate your program immediately.### Notes
- For each output, add a newline at the end and flush Standard Output. Otherwise, you may receive a TLE verdict.
- If your program prints output in an incorrect format during the interaction or terminates prematurely, the verdict is indeterminate.
- After processing the last test case, terminate your program immediately. Otherwise, the verdict is indeterminate.
- The judge of this problem is not adaptive. The judge fixes the set A for every test case before the interaction.
Constraints
- 1≤T≤5×104
- 4≤N≤2×105
- The sum of N over all test cases is at most 2×105.
- All input values are integers.
交互
这是一个交互式问题(你的程序需通过标准输入/输出与评测系统进行交互)。
首先,从标准输入读取测试用例数量 T。
T
随后,输入 T 个测试用例。每个测试用例按如下流程进行:
从标准输入读取整数 N。
N
接着,你最多可提出 ⌊43N⌋ 个问题。每个问题需按如下格式输出至标准输出:
? a
其中,a 必须满足以下条件:
- 1≤a≤N−1
- a 为整数。
作为回应,若 a 属于集合 A,则标准输入将返回 Yes;否则返回 No。
然而,若 a 不满足上述条件,或提问次数超过 ⌊43N⌋,则评测系统将返回 -1。
若评测系统返回 -1,则你的程序已被视为错误。此时请立即终止程序。
令 S=−1 表示集合 A 中不存在特殊子集;否则令 S 为特殊子集的最小元素个数。
当你确定 S 后,请按如下格式将其输出至标准输出:
! S
然后继续处理下一个测试用例(若存在)。在处理完最后一个测试用例后,请立即终止程序。
注意事项
- 每次输出后必须添加换行符,并刷新标准输出。否则可能收到 TLE 判定。
- 若你的程序在交互过程中输出格式错误,或提前终止,则判定结果为不确定(indeterminate)。
- 处理完最后一个测试用例后,请立即终止程序。否则判定结果为不确定(indeterminate)。
- 本题评测器为非自适应型(non-adaptive):对于每个测试用例,评测器会在交互开始前预先固定集合 A。
约束条件
- 1≤T≤5×104
- 4≤N≤2×105
- 所有测试用例中 N 的总和不超过 2×105。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?