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,…,pn of numbers from 1 to n from you, where n is even. You can try to guess it using the following queries:
? k a1 a2 … ak.
In response, you will learn if the average of elements with indexes a1,a2,…,ak is an integer. In other words, you will receive 1 if kpa1+pa2+⋯+pak is integer, and 0 otherwise.
You have to guess the permutation. You can ask not more than 18n queries.
Note that permutations [p1,p2,…,pk] and [n+1−p1,n+1−p2,…,n+1−pk] are indistinguishable. Therefore, you are guaranteed that p1≤2n.
Note that the permutation p 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.
本题为交互式问题。
我们隐藏了一个由 1 到 n 构成的排列 p1,p2,…,pn,其中 n 为偶数。你可以通过以下查询尝试猜出该排列:
? k a1 a2 … ak。
作为回应,你将得知下标为 a1,a2,…,ak 的元素的平均值是否为整数。换言之,若 kpa1+pa2+⋯+pak 是整数,则返回 1;否则返回 0。
你需要猜出该排列。你至多可进行 18n 次查询。
注意:排列 [p1,p2,…,pk] 与 [n+1−p1,n+1−p2,…,n+1−pk] 在查询下不可区分。因此,题目保证 p1≤2n。
注意:排列 p 在交互开始前即已固定,且不依赖于你的查询。换言之,交互器是非自适应的(non-adaptive)。
注意:你无需最小化查询次数。
输入格式
The first line contains a single integer n (2≤n≤800, n is even).
第一行包含一个整数 n(2≤n≤800,且 n 为偶数)。
输入输出样例
输入#1
2 1 2
输出#1
? 1 2 ? 1 1 ! 1 2
输入解题思路,AI测评打分。不知道怎么写?