D - Magician 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 1400 点

問題文

これはインタラクティブな問題です。

机の上に {}_{2N}\mathrm{C}_N 枚のカードがあり、1 から {}_{2N}\mathrm{C}_N までの番号が付けられています。カード i (1 \leq i \leq {}_{2N}\mathrm{C}_N) のオモテ面には、N 個の 0 と N 個の 1 からなる {}_{2N}\mathrm{C}_N 種類の文字列のうち、辞書順で i 番目に小さいものが印刷されています。

具体例たとえば N=2 の場合、カード 1, 2, 3, 4, 5, 6 のオモテ面にはそれぞれ 0011、0101、0110、1001、1010、1100 が印刷されます。


魔女の Alice は、各カードのウラ面に最初の N 個の英大文字（たとえば N=2 の時 A, B）のいずれかを書き、その後以下のマジックを T 回行います。

一回のマジックの流れ

  1. 司会者が、最初の N 個の英大文字のいずれか s を宣言する。
  2. 司会者が、黒板に 0 のみからなる長さ 2N の文字列を書く。
  3. i = 1, 2, \dots, N の順に以下の行動を行う。ただし a_1, b_1, \dots, a_N, b_N は 1 以上 2N 以下の相異なる整数である。
    • まず、司会者が Alice に整数 a_i と b_i を伝える。
    • 次に、Alice が黒板の文字列の a_i 文字目と b_i 文字目のうち片方だけを 1 に変える。
  4. 黒板の文字列を x とする。x がオモテ面に書き込まれたカードがちょうど一枚あるので、そのウラ面を見る。ウラ面に書かれた文字が s であれば、マジックは成功、そうでなければマジックは失敗である。

ここで、Alice は a_i 文字目と b_i 文字目のうち片方を 1 に変えるまで、a_{i+1}, b_{i+1} の情報を知ることができないことに注意する必要があります。

T 回すべてのマジックで成功する戦略を実装してください。では、始めましょう。

制約

  • 2 \leq N \leq 10
  • 1 \leq T \leq 5\,000
  • s は最初の N 個の英大文字のいずれかである
  • 1 \leq a_i < b_i \leq 2N
  • a_1, b_1, a_2, b_2, \dots, a_N, b_N は相異なる
  • a_1, b_1, a_2, b_2, \dots, a_N, b_N, s はジャッジとの対話前に決定される
  • N, T, a_i, b_i は整数

入出力

最初に、整数 N, T を標準入力から以下の形式で受け取ってください。

N T

次に、カード i のウラ面に書き込む文字を c_i とするとき、以下の形式で出力してください。末尾に改行を入れてください。ここで、c_i は最初の N 個の英大文字のいずれかである必要があります。

c_1 c_2 \cdots c_{{}_{2N}\mathrm{C}_N}

次に、以下の処理を T 回繰り返してください。t 回目 (1 \leq t \leq T) の処理は t 回目のマジックに対応します。

まず、司会者が宣言した文字 s を以下の形式で標準入力から受け取る。

s

続いて、i = 1, 2, \dots, N の順に以下の処理を行う。

  • まず、整数 a_i, b_i を以下の形式で入力する。

a_i b_i

  • 次に、1 に変える文字の位置 d を、以下の形式で出力する。d は a_i, b_i のいずれかでなければならない。末尾に改行を入れること。

d

ここで、出力形式にミスがあった場合や、前回のマジックに失敗した場合、それ以降 s や (a_i, b_i) などの入力は与えられず、-1 が標準入力から与えられる。この場合はただちにプログラムを終了すること。（ただし、T 回目のマジックで初めて失敗した場合や、T 回目のマジックの i = N のときに初めて出力形式にミスがあった場合は、その後の入力は何も与えられない）

注意点

出力を行うたびに、ジャッジ結果を flush してください。そうしなかった場合、ジャッジ結果が TLE となることがあります。

また、ジャッジから -1 という入力を受け取った場合はただちにプログラムを終了してください。終了した場合のジャッジ結果は WA となりますが、終了しなかった場合のジャッジ結果は不定です。さらに、余計な改行は不正な形式の出力とみなされることがあるので注意してください。

この問題のジャッジシステムは適応的 (adaptive) ではありません。すなわち、a_1, b_1, a_2, b_2, \dots, a_N, b_N, s の値はジャッジとの対話前に決定され、プログラムの出力によって変更されることはありません。

入出力例

以下に示す例は、対話の一例であることに注意してください。

入力 出力 説明
2 2 まず整数 N と T が標準入力から与えられます。
ABABAB 6 枚のカードに書き込む文字を出力します。
A 1 回目のマジックが始まります。
司会者は文字 A を宣言します。
1 2 (a_1, b_1) = (1, 2) であることが司会者から知らされます。
2 黒板の 2 文字目を 1 にします。
3 4 (a_2, b_2) = (3, 4) であることが司会者から知らされます。
3 黒板の 3 文字目を 1 にします。
最終的な黒板の文字列は 0110 となり、オモテ面に 0110 と書かれたカードのウラ面は A なのでマジック成功です。
B 2 回目のマジックが始まります。
司会者は文字 B を宣言します。
1 3 (a_1, b_1) = (1, 3) であることが司会者から知らされます。
1 黒板の 1 文字目を 1 にします。
2 4 (a_2, b_2) = (2, 4) であることが司会者から知らされます。
2 黒板の 2 文字目を 1 にします。
最終的な黒板の文字列は 1100 となり、オモテ面に 1100 と書かれたカードのウラ面は B なのでマジック成功です。

Score : 1400 points

Problem Statement

This is an interactive problem.

There are \tbinom{2N}{N} cards numbered 1 to \tbinom{2N}{N} on a desk. Card i (1 \le i \le \tbinom{2N}{N}) shows on its front the i‑th string in lexicographic order among the strings consisting of N zeros and N ones.

Example For N = 2, the fronts of cards 1, 2, 3, 4, 5, 6 are 0011, 0101, 0110, 1001, 1010, 1100, respectively.


Witch Alice writes one of the first N uppercase letters (for example, A or B if N = 2) on the back of each card, then performs the following magic T times.

A single magic

  1. The host announces a letter s among the first N uppercase letters.
  2. The host writes a length-2N string of all 0 on the blackboard.
  3. For i = 1, 2, \dots, N in this order, do the following. Here, a_1, b_1, \dots, a_N, b_N are distinct integers from 1 to 2N.
    • First, the host tells Alice integers a_i and b_i.
    • Then, Alice chooses exactly one of the a_i-th and b_i-th characters of the string on the blackboard, and sets it to 1.
  4. Let x be the final string on the blackboard. Exactly one card shows x on its front; look at its back. The magic succeeds if and only if the letter on its back equals s.

Note that Alice learns a_{i+1} and b_{i+1} only after choosing which of the a_i-th and b_i-th characters to set to 1.

Implement a strategy that makes all T magics succeed. Now, let us begin.

Constraints

  • 2 \le N \le 10
  • 1 \le T \le 5\,000
  • The letter s is among the first N uppercase letters.
  • 1 \le a_i < b_i \le 2N
  • a_1, b_1, a_2, b_2, \dots, a_N, b_N are distinct.
  • a_1, b_1, a_2, b_2, \dots, a_N, b_N, s are fixed before the interaction starts.
  • N, T, a_i, b_i are integers.

Input and Output

First, read the integers N and T given from Standard Input in the following format:

N T

Next, let c_i be the letter written on the back of card i, and print those letters in the following format, followed by a newline. Here, c_i must be among the first N uppercase letters.

c_1 c_2 \cdots c_{\tbinom{2N}{N}}

Next, repeat the following process T times. The t-th iteration (1 \leq t \leq T) corresponds to the t-th magic.

Read the announced letter s given in the following format:

s

Then, for i = 1, 2, \dots, N in this order, do the following.

  • Read integers a_i and b_i given in the following format:

a_i b_i

  • Print the chosen position d in the following format, followed by a newline. Here, d must be a_i or b_i.

d

If your output was malformed or the previous magic failed, no more input such as s or (a_i, b_i) is given, but -1 is given from Standard Input. In this case, exit immediately. (If you fail for the first time in the T-th magic, or your output was malformed for the first time at i = N in the T-th magic, no more input follows.)

Notes

Flush after every output. Otherwise, you may receive a TLE verdict.

If you read -1, exit immediately. If you do so, you will receive a WA verdict, but continuing leads to an indeterminate verdict. Unnecessary newlines may be seen as malformed.

The judge is non‑adaptive; the values a_1, b_1, a_2, b_2, \dots, a_N, b_N, s are fixed before the interaction starts, and will not be affected by your output.

Sample Interaction

Note that this is just an example of interaction.

InputOutputComment
2 2The integers N and T are given from Standard Input.
ABABABPrint letters for the backs of the six cards.
AThe first magic begins.
The host declares A.
1 2The host tells you (a_1, b_1) = (1, 2).
2Set the second character to 1.
3 4The host tells you (a_2, b_2) = (3, 4).
3Set the third character to 1.
The final string is 0110, and the card with 0110 on its front has A on the back, so the magic succeeds.
BThe second magic begins.
The host declars B.
1 3The host tells you (a_1, b_1) = (1, 3).
1Set the first character to 1.
2 4The host tells you (a_2, b_2) = (2, 4).
2Set the second character to 1.
The final string is 1100, and the card with 1100 on its front has B on the back, so the magic succeeds.