F - Guess The Number 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

あなたとジャッジは下記の手順を行います。 手順はフェイズ 1 とフェイズ 2 からなり、まずフェイズ 1 を行った直後、続けてフェイズ 2 を行います。

（フェイズ 1 ）

  • ジャッジが 1 以上 10^9 以下の整数 N を決める。この整数は隠されている。
  • あなたは 1 以上 110 以下の整数 M を出力する。
  • さらにあなたは、すべての i = 1, 2, \ldots, M について 1 \leq A_i \leq M を満たす、長さ M の整数列 A=(A_1,A_2,\ldots,A_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 を出力する。

上記の手順を行った後、直ちにプログラムを終了することで正解となります。

制約

  • N は 1 以上 10^9 以下の整数

入出力

この問題はインタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

（フェイズ 1 ）

  • まず、1 以上 110 以下の整数 M を出力してください。出力後、必ず改行してください。
M
  • その後、空白区切りで 1 以上 M 以下の整数からなる長さ M の整数列 A=(A_1,A_2,\ldots,A_M) を出力してください。出力後、必ず改行してください。
A_1 A_2 \ldots A_M

（フェイズ 2 ）

  • まず、長さ M の整数列 B=(B_1,B_2,\ldots,B_M) が入力から与えられます。
B_1 B_2 \ldots B_M
  • 整数 N を求め、出力してください。出力後、必ず改行してください。
N

不正な出力がなされた場合、ジャッジは -1 を出力します。この時、提出はすでに不正解と判定されています。ジャッジプログラムはこの時点で終了するため、あなたのプログラムも終了するのが望ましいです。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
  • 答えを出力したら(または -1 を受け取ったら)直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。
  • 特に、余計な改行も不正なフォーマットの出力とみなされるので注意してください。

入出力例

以下は、N = 2 の場合の入出力例です。

入力 出力 説明
ジャッジは N=2 と決めました。N は入力としては与えられず、隠されています。
4 M を出力します。
2 3 4 4 A=(2,3,4,4) を出力します。
3 4 4 4 f^2(1)=3,f^2(2)=4,f^2(3)=4,f^2(4)=4 なので、ジャッジは B=(3,4,4,4) をあなたのプログラムに与えます。
2 B から N=2 であると特定しました。 N を出力し、プログラムを正常終了させてください。

Score : 500 points

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.