分数: 600 点
问题陈述
准备尽可能少的天梯彩票类型,并将它们组合起来,以便可以产生所有排列。
这是一个 交互问题 (其中您的程序和判断程序通过输入和输出进行交互)。
给你一个正整数 N.
选择任何正整数 m 和 m 的排列 (1,2,\dots,N),并输出它们。让 i-th 排列为 P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}).
然后,一个排列 给出了 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) 。输出正整数序列 A=(A_1,A_2,\dots,A_k) 满足以下所有条件。
- 0 \le k \le 2N^2
- 的所有元素 A 之间 1 和 m,包括在内。
- 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
- 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.
让 m_{\min} 是最小值 m 无论怎样都可以解决上述问题 Q。你的输出 m 必须等于 m_{\min}.
更准确地说
对于一系列排列 P=(P_1,P_2,\dots,P_m) of (1,2,\dots,N),我们称之为 P a 良好的排列顺序 如果满足以下条件:- 对于任何排列 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N),存在正整数序列 A=(A_1,A_2,\dots,A_k) 满足以下所有条件。
- 0 \le k \le 2N^2
- 的所有元素 A 之间 1 和 m,包括在内。
- 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
- 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.
请注意您的输出 P 不需要是 良好的排列顺序。如果您能输出一个,则认为您的提交是正确的 A 满足给定的条件 Q.
约束
- 3 \le N \le 500
- Q 是一个排列 (1,2,\dots,N).
- 所有输入值均为整数。
输入/输出
这是一个 交互问题 (其中您的程序和判断程序通过输入和输出进行交互)。
首先,法官给你一个正整数 N 采用以下格式:
N
然后,输出你选择的正整数 m 和 m 的排列 (1,2,\dots,N) 格式如下 m+1 行。在这里, j- 第一个元素 i-th 排列是 P_{i,j}。确保在最后输出换行符。
m
P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}
P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}
\vdots
P_{m,1}\ P_{m,2}\ \dots\ P_{m,N}
必须满足以下条件:
- m \le 1000
- (P_{i,1},P_{i,2},\dots,P_{i,N}) 是一个排列 (1,2,\dots,N).
如果你的输出 P 不满足上述条件,则判断输出 -1。此时,您的提交已被判定为不正确。判断程序将在此时终止,因此建议您的程序也终止。
然后,法官给你一个排列 Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) 采用以下格式:
Q_1\ Q_2\ \dots\ Q_N
然后,输出一个正整数序列 A=(A_1,A_2,\dots,A_k) 采用以下格式。确保在最后输出换行符。
k\ A_1\ A_2\ \dots\ A_k
当且仅当以下条件全部满足时,您的输出才会被判断为正确:
- m = m_{\min}
- 0 \le k \le 2N^2
- 的所有元素 A 之间 1 和 m,包括在内。
- 从序列开始 R=(1,2,\dots,N),执行以下操作 i = 1,2,\dots,k 按顺序导致 R = Q.
- 让 p = P_{A_i}。同时更换 R_{j} 与 R_{p_j} 对于每个 j = 1,2,\dots,N.
注释
- 在每个输出之后,插入换行符并刷新标准输出。如果不这样做,可能会导致法官做出以下判决: TLE.
- 如果您收到
-1,立即终止您的程序。如果你这样做,法官的判决将是 WA,但如果你不这样做,法官的判决将是不确定的。 - 输出答案后立即终止程序。否则,法官的判决将是不确定的。
- 不要输出不必要的换行符,因为它们将被视为格式错误。
- 这个问题的判断不是自适应的。判断程序决定 Q 在互动开始之前。
示例输入/输出
以下是一个案例 N=3,Q=(2,3,1).
| 输入 | 输出 | 说明 |
|---|---|---|
3 |
N 。 | |
2
|
选择 m = 2,P_1=(2,1,3),P_2=(3,2,1) 并输出它们。 | |
2 3 1 |
自从 P 满足条件, Q=(2,3,1) 。 | |
2 2 1
|
A=(2,1) 满足条件。 R 变为 (1,2,3) \rightarrow (3,2,1) \rightarrow (2,3,1),匹配 Q. 另外, m_{\min} = 2 为 N = 3,和 m = m_{\min} 很满意。 因此,该输出被判断为正确。 一定要输出 k 也一样,都在一行上。 |