尺寸 N 的排列是一个数字序列。 这是 (1, 2, 3, …, N) 每个元素的重新排列。 例如 (5, 2, 1, 4, 3) 是尺寸 它是 5 的排列,但另一方面 (1, 5, 1, 2, 3) 不是。
这个问题是一个反应性任务。您与响应程序玩“排列猜测游戏”。 首先,响应程序是一个排列 内部确定一个 σ。 然后你就得到了这个排列的大小 N 已发送。 此后,您将多次返回响应程序。 执行質問。 您的目标是确定响应程序的排列。
问题如下: 尺寸 N 的排列 决定一个 τ 并将其询问给响应程序。 响应程序是一个数字序列。 ai = (σ上面的数字 i 位置和 τ 上面的数字 i 位置距离 计算)。 然后是顺序 (a1, a2, a3, …, aN) 按升序排列 创建 (b1, b2, b3, …, bN) 并将其输出到您的程序。
例如, 当σ = (5, 2, 1, 4, 3) 时, 当你听τ = (2, 3, 1, 4, 5) 时, 响应程序是内部的 计算 (a1, a2, a3, a4, a5) = (0, 1, 3, 0, 4) 并 对此进行排序的列 (b1, b2, b3, b4, b5) = (0, 0, 1, 3, 4) 。
编写一个程序,用尽可能少的问题来识别排列。 评分方法在“评分方法”部分中描述。
入出力形式
一、排列的大小 N 作为输入给出。
N
然后,您的程序会多次询问响应程序。问题的格式如下。
? τ1 τ2 τ3 … τN
b1 b2 b3 … bN
在代码中实现此交互时,在 C++ 中,它看起来像这样,例如: 例如排列 例如,如果您想询问 (5, 2, 1, 4, 3) , 做类似
int tau[5] = {5, 2, 1, 4, 3};
printf("?");
for (int i=0; i<5; ++i) printf(" %d", tau[i]);
printf("\n");
fflush(stdout);
的事情。下一步
for (int i=0; i<5; ++i) scanf("%d", &b[i]);
返回数组 b 中问题的答案。
提出几个问题后,您可以确定响应程序的排列。
识别 σ 。格式如下。
(与问题的格式几乎相同,第一个
请注意,它是 ? 是 ! 。 )
! τ1 τ2 τ3 … τN
本题中,为每个测试数据设置了提问数量上限,如果程序提问数量超过上限,则会被判定为错误答案。
制約
- 1 ≤ N ≤ 400
採点方式
- 在50分的测试用例组中,问题数量上限为1000道。
- 对于750分的测试用例组,问题数量上限为240道。
入出力例1
| プログラムの出力 | プログラムへの入力 |
|---|---|
| 5 | |
| ? 2 3 1 4 5 | |
| 0 0 1 3 4 | |
| ? 1 2 3 4 5 | |
| 0 0 2 2 4 | |
| ? 5 4 3 2 1 | |
| 0 2 2 2 2 | |
| ? 5 2 1 4 3 | |
| 0 0 0 0 0 | |
| ! 5 2 1 4 3 |
σ = (5, 2, 1, 4, 3) 。该专栏是在提出几个问题后确定的。
入出力例2
| プログラムの出力 | プログラムへの入力 |
|---|---|
| 1 | |
| ! 1 |
由于大小为 1 的排列只有一种,因此无需提出任何问题即可立即识别。