Score : $500$ points

问题描述

这是一个 交互式任务，你编写的程序和裁判程序将通过标准输入和输出进行交互。

你们将按照以下步骤进行操作。该过程包括阶段1和阶段2，阶段1紧接阶段2。

(阶段1)

• 裁判决定一个整数 $N$，其范围在 $1$ 到 $10^9$（包含）之间，但这个值是隐藏的。
• 你打印一个整数 $M$，其范围在 $1$ 到 $110$（包含）之间。
• 你还需打印一个长度为 $M$ 的整数序列 $A=(A_1,A_2,\ldots,A_M)$，其中对于所有 $i = 1, 2, \ldots, M$，满足 $1 \leq A_i \leq M$。

(阶段2)

• 裁判给你一个长度为 $M$ 的整数序列 $B=(B_1,B_2,\ldots,B_M)$。这里，$B_i = f^N(i)$。函数 $f(i)$ 定义为对于所有在 $1$ 和 $M$（包含）之间的整数 $i$，都有 $f(i)=A_i$，而 $f^N(i)$ 是通过将 $i$ 替换为 $f(i)$ 连续进行 $N$ 次后得到的整数。
• 根据给出的 $B$ 序列，你需要识别出裁判所决定的整数 $N$，并打印出 $N$。

完成上述步骤后，请立即终止程序以接受正确性判断。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases $1$ and $2$; phase $1$ is immediately followed by phase $2$.

(Phase $1$)

• The judge decides an integer $N$ between $1$ and $10^9$ (inclusive), which is hidden.
• You print an integer $M$ between $1$ and $110$ (inclusive).
• You also print an integer sequence $A=(A_1,A_2,\ldots,A_M)$ of length $M$ such that $1 \leq A_i \leq M$ for all $i = 1, 2, \ldots, M$.

(Phase $2$)

• The judge gives you an integer sequence $B=(B_1,B_2,\ldots,B_M)$ of length $M$. Here, $B_i = f^N(i)$. $f(i)$ is defined by $f(i)=A_i$ for all integers $i$ between $1$ and $M$ (inclusive), and $f^N(i)$ is the integer resulting from replacing $i$ with $f(i)$ $N$ times.
• Based on the given $B$, you identify the integer $N$ that the judge has decided, and print $N$.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• $N$ is an integer between $1$ and $10^9$ (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase $1$)

• First, print an integer $M$ between $1$ and $110$ (inclusive). It must be followed by a newline.

$M$

• Then, print a sequence $A=(A_1,A_2,\ldots,A_M)$ of length $M$ consisting of integers between $1$ and $M$ (inclusive), with spaces in between. It must be followed by a newline.

$A_1$ $A_2$ $\ldots$ $A_M$

(Phase $2$)

• First, an integer sequence $B=(B_1,B_2,\ldots,B_M)$ of length $M$ is given from the input.

$B_1$ $B_2$ $\ldots$ $B_M$

• Find the integer $N$ and print it. It must be followed by a newline.

$N$

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with $N = 2$.

Input	Output	Description
		The judge has decided that $N=2$. $N$ is hidden: it is not given as an input.
	4	You print $M$.
	2 3 4 4	You print $A=(2,3,4,4)$.
3 4 4 4		$f^2(1)=3,f^2(2)=4,f^2(3)=4$, and $f^2(4)=4$, so the judge gives $B=(3,4,4,4)$ to your program.
	2	Based on $B$, you have identified that $N=2$. Print $N$ and terminate the program normally.

update @ 2024/3/10 11:58:26