F - Union of Two Sets Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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

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

（フェイズ 1 ）

  • ジャッジから整数 N が与えられる。
  • あなたは 1 以上 50000 以下の整数 M を出力する。
  • さらにあなたは、すべての i = 1, 2, \ldots, M について 1 \leq l_i \leq r_i \leq N を満たす、M 個の整数の組 (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) を出力する（M 個の整数の組が相異なる必要はない）。

（フェイズ 2 ）

  • ジャッジから整数 Q が与えられる。
  • その後、あなたとジャッジは下記の手順を Q 回繰り返す。
    • ジャッジからクエリとして 2 つの整数 L, R が与えられる。
    • それに対する応答として、あなたは 1 以上 M 以下の 2 つの整数 a, b を出力する（ a = b でもよい）。 このとき、a と b は下記の条件を満たさなければならない。もし満たさなかった場合は不正解となる。
      • 集合 \lbrace l_a, l_a+1, \ldots, r_a\rbrace と集合 \lbrace l_b, l_b+1, \ldots, r_b\rbrace の和集合が、集合 \lbrace L, L+1, \ldots, R\rbrace と一致する。

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

制約

  • 1 \leq N \leq 4000
  • 1 \leq Q \leq 10^5
  • 1 \leq L \leq R \leq N
  • 入力はすべて整数

入出力

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

（フェイズ 1 ）

  • まず、N が入力から与えられます。
  • 次に、1 以上 50000 以下の整数 M を出力してください。
  • その後、M 回にわたって (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) を出力してください。 具体的には、i = 1, 2, \ldots, M について、i 回目の出力では (l_i, r_i) を下記の形式で出力してください。
l_i r_i

（フェイズ 2 ）

  • まず、Q が入力から与えられます。
  • 各クエリでは、クエリを表す整数 L, R が下記の形式で与えられます。
L R
  • 各クエリに対する応答では、2 つの整数 a, b を下記の形式で出力してください。
a b

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果が ではなく や TLE になる可能性があることに注意してください。
  • フェイズ 2 を終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
  • フェイズ 2 で与えられる L, R は、あなたがフェイズ 1 で出力した (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) に応じて決定されます。

入出力例

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

入力 出力 説明
4 N が与えられます。
6 M を出力します。
3 3 (l_1, r_1) = (3, 3) を出力します。
4 4 (l_2, r_2) = (4, 4) を出力します。
1 1 (l_3, r_3) = (1, 1) を出力します。
2 4 (l_4, r_4) = (2, 4) を出力します。
1 3 (l_5, r_5) = (1, 3) を出力します。
2 2 (l_6, r_6) = (2, 2) を出力します。
4 Q が与えられます。
1 3 1 個目のクエリとして L = 1, R = 3 が与えられます。
1 5 1 個目のクエリに対する応答として a = 1, b = 5 を出力します。
3 4 2 個目のクエリとして L = 3, R = 4 が与えられます。
2 1 2 個目のクエリに対する応答として a = 2, b = 1 を出力します。
2 4 3 個目のクエリとして L = 2, R = 4 が与えられます。
4 4 3 個目のクエリに対する応答として a = 4, b = 4 を出力します。
1 1 4 個目のクエリとして L = 1, R = 1 が与えられます。
3 3 4 個目のクエリに対する応答として a = 3, b = 3 を出力します。

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 gives you an integer N.
  • You print an integer M between 1 and 50000, inclusive.
  • You also print M pairs of integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) such that 1 \leq l_i \leq r_i \leq N for every i = 1, 2, \ldots, M (the M pairs do not have to be distinct).

(Phase 2)

  • The judge gives you an integer Q.
  • You and the judge repeats the following Q times.
    • The judge gives you two integers L and R as a query.
    • You respond with two integers a and b between 1 and M, inclusive (possibly with a = b). Here, a and b must satisfy the condition below. Otherwise, your submission will be judged incorrect.
      • The union of the set \lbrace l_a, l_a+1, \ldots, r_a\rbrace and the set \lbrace l_b, l_b+1, \ldots, r_b\rbrace equals the set \lbrace L, L+1, \ldots, R\rbrace.

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

Constraints

  • 1 \leq N \leq 4000
  • 1 \leq Q \leq 10^5
  • 1 \leq L \leq R \leq N
  • All values in the input are integers.

Input and Output

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

(Phase 1)

  • First, N is given from the input.
  • Next, an integer M between 1 and 50000, inclusive, should be printed.
  • Then, (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) should be printed, one at a time. Specifically, for each i = 1, 2, \ldots, M, the i-th output should be (l_i, r_i) in the following format:
l_i r_i

(Phase 2)

  • First, Q is given from the input.
  • In each query, integers L and R representing the query are given in the following format:
L R
  • In response to each query, two integers a and b should be printed in the following format:
a b

Cautions

  • At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE verdict.
  • If your program prints a malformed output or quits prematurely, the verdict will be indeterminate. Particularly, note that in case of a runtime error, the verdict may be or TLE instead of .
  • After phase 2, immediately terminate the program. Otherwise, the verdict will be indeterminate.
  • L and R given in phase 2 will be decided according to (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) you print in phase 1.

Sample Interaction

Below is a sample interaction with N = 4 and Q = 4.

Input Output Description
4 N is given.
6 You print M.
3 3 You print (l_1, r_1) = (3, 3).
4 4 You print (l_2, r_2) = (4, 4).
1 1 You print (l_3, r_3) = (1, 1).
2 4 You print (l_4, r_4) = (2, 4).
1 3 You print (l_5, r_5) = (1, 3).
2 2 You print (l_6, r_6) = (2, 2).
4 Q is given.
1 3 As the first query, L = 1 and R = 3 are given.
1 5 You respond with a = 1 and b = 5.
3 4 As the second query, L = 3 and R = 4 are given.
2 1 You respond with a = 2 and b = 1.
2 4 As the third query, L = 2 and R = 4 are given.
4 4 You respond with a = 4 and b = 4.
1 1 As the fourth query, L = 1 and R = 1 are given.
3 3 You respond with a = 3 and b = 3.