CF1299E.So Mean

NOI/NOI+/CTSC

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

This problem is interactive.

We have hidden a permutation p1,p2,…,pnp_1, p_2, \dots, p_n of numbers from 11 to nn from you, where nn is even. You can try to guess it using the following queries:

?? kk a1a_1 a2a_2 …\dots aka_k.

In response, you will learn if the average of elements with indexes a1,a2,…,aka_1, a_2, \dots, a_k is an integer. In other words, you will receive 11 if pa1+pa2+⋯+pakk\frac{p_{a_1} + p_{a_2} + \dots + p_{a_k}}{k} is integer, and 00 otherwise.

You have to guess the permutation. You can ask not more than 18n18n queries.

Note that permutations [p1,p2,…,pk][p_1, p_2, \dots, p_k] and [n+1−p1,n+1−p2,…,n+1−pk][n + 1 - p_1, n + 1 - p_2, \dots, n + 1 - p_k] are indistinguishable. Therefore, you are guaranteed that p1≤n2p_1 \le \frac{n}{2}.

Note that the permutation pp is fixed before the start of the interaction and doesn't depend on your queries. In other words, interactor is not adaptive.

Note that you don't have to minimize the number of queries.

本题为交互式问题。

我们隐藏了一个由 11 到 nn 构成的排列 p1,p2,…,pnp_1, p_2, \dots, p_n,其中 nn 为偶数。你可以通过以下查询尝试猜出该排列:

?? kk a1a_1 a2a_2 …\dots aka_k。

作为回应,你将得知下标为 a1,a2,…,aka_1, a_2, \dots, a_k 的元素的平均值是否为整数。换言之,若 pa1+pa2+⋯+pakk\frac{p_{a_1} + p_{a_2} + \dots + p_{a_k}}{k} 是整数,则返回 11;否则返回 00。

你需要猜出该排列。你至多可进行 18n18n 次查询。

注意:排列 [p1,p2,…,pk][p_1, p_2, \dots, p_k] 与 [n+1−p1,n+1−p2,…,n+1−pk][n + 1 - p_1, n + 1 - p_2, \dots, n + 1 - p_k] 在查询下不可区分。因此,题目保证 p1≤n2p_1 \le \frac{n}{2}。

注意:排列 pp 在交互开始前即已固定,且不依赖于你的查询。换言之,交互器是非自适应的(non-adaptive)。

注意:你无需最小化查询次数。

输入格式

The first line contains a single integer nn (2≤n≤8002 \le n \le 800, nn is even).

第一行包含一个整数 nn(2≤n≤8002 \le n \le 800,且 nn 为偶数)。

输入输出样例

  • 输入#1

    2
    1 2

    输出#1

    ? 1 2
    ? 1 1
    ! 1 2

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

首页