← 返回题目列表

AtCoder · kupc2013_i

I. 西格玛

中文机器翻译题面 查看原题
我们收到报告称此问题评分不正确。

尺寸 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
τi 是问题的排列 这是第 i 个元素的值。 此时 它必须是 (τ1, …, τN) 是尺寸 它是 N 的排列。 也就是说,τi 的值为 1 以上 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 的排列只有一种,因此无需提出任何问题即可立即识别。