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 NN.

For a set XX of positive integers, a subset of XX whose sum is NN is called a special subset of XX.

The judge system has a hidden set AA that satisfies all of the following conditions, but you cannot directly know the values of the elements of AA.

  • ∣A∣=⌊N2⌋|A|=\left\lfloor\frac{N}{2}\right\rfloor
  • Every element of AA is an integer between 11 and N−1N-1, inclusive.

You may ask the judge system the following question at most ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor times.

  • Choose an integer aa between 11 and N−1N-1, inclusive, and ask whether aa is contained in AA.

Determine whether the hidden set AA has a special subset, and if it does, find the minimum number of elements in a special subset.

Solve TT test cases for each input.

这是一个交互式问题(你的程序需通过标准输入和输出与评测系统进行交互)。

你将得到一个正整数 NN。

对于一个正整数集合 XX,若其某个子集的元素之和等于 NN,则该子集称为 XX 的一个特殊子集。

评测系统内部隐藏了一个集合 AA,它满足以下所有条件,但你无法直接得知 AA 中各元素的具体取值:

  • ∣A∣=⌊N2⌋|A|=\left\lfloor\frac{N}{2}\right\rfloor
  • AA 中每个元素均为介于 11 和 N−1N-1(含端点)之间的整数。

你最多可向评测系统提出 ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor 次如下形式的询问:

  • 选择一个介于 11 和 N−1N-1(含端点)之间的整数 aa,询问 aa 是否属于 AA。

请判断隐藏集合 AA 是否存在特殊子集;若存在,请找出特殊子集中元素个数的最小值。

对每组输入,需解决 TT 个测试用例。

说明/提示

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 TT from Standard Input.

TT

Then, TT test cases follow. Each test case proceeds as follows.

Receive the integer NN from Standard Input.

NN

Then, you may ask at most ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor questions. Print each question to Standard Output in the following format:

?? aa

Here, aa must satisfy the following:

  • 1≤a≤N−11 \leq a \leq N-1
  • aa is an integer.

In response, Yes is given from Standard Input if aa is contained in AA, and No is given otherwise.

However, if aa does not satisfy the conditions above, or if the number of questions exceeds ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor, -1 is returned.

If the judge returns -1, your program is already considered incorrect. In this case, terminate your program immediately.

Let S=−1S=-1 if AA has no special subset; otherwise, let SS be the minimum number of elements in a special subset.
Once you have found SS, print it to Standard Output in the following format.

!! SS

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 AA for every test case before the interaction.

Constraints

  • 1≤T≤5×1041 \leq T \leq 5 \times 10^4
  • 4≤N≤2×1054 \leq N \leq 2 \times 10^5
  • The sum of NN over all test cases is at most 2×1052 \times 10^5.
  • All input values are integers.

交互

这是一个交互式问题(你的程序需通过标准输入/输出与评测系统进行交互)。

首先,从标准输入读取测试用例数量 TT。

TT

随后,输入 TT 个测试用例。每个测试用例按如下流程进行:

从标准输入读取整数 NN。

NN

接着,你最多可提出 ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor 个问题。每个问题需按如下格式输出至标准输出:

?? aa

其中,aa 必须满足以下条件:

  • 1≤a≤N−11 \leq a \leq N-1
  • aa 为整数。

作为回应,若 aa 属于集合 AA,则标准输入将返回 Yes;否则返回 No。

然而,若 aa 不满足上述条件,或提问次数超过 ⌊3N4⌋\left\lfloor\frac{3N}{4}\right\rfloor,则评测系统将返回 -1。

若评测系统返回 -1,则你的程序已被视为错误。此时请立即终止程序。

令 S=−1S = -1 表示集合 AA 中不存在特殊子集;否则令 SS 为特殊子集的最小元素个数。
当你确定 SS 后,请按如下格式将其输出至标准输出:

!! SS

然后继续处理下一个测试用例(若存在)。在处理完最后一个测试用例后,请立即终止程序。

注意事项

  • 每次输出后必须添加换行符,并刷新标准输出。否则可能收到 TLE 判定。
  • 若你的程序在交互过程中输出格式错误,或提前终止,则判定结果为不确定(indeterminate)。
  • 处理完最后一个测试用例后,请立即终止程序。否则判定结果为不确定(indeterminate)。
  • 本题评测器为非自适应型(non-adaptive):对于每个测试用例,评测器会在交互开始前预先固定集合 AA。

约束条件

  • 1≤T≤5×1041 \leq T \leq 5 \times 10^4
  • 4≤N≤2×1054 \leq N \leq 2 \times 10^5
  • 所有测试用例中 NN 的总和不超过 2×1052 \times 10^5。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页