F Typical Encoder

制限時間: 2 sec メモリ制限: 1024 MB

Typical Encoder

Statement

\(2\) つのプログラム Alice, Bob が協力してゲームを \(T\) 回行います。

各ゲームは次のように行われます。

\(0\) 以上 \(10^{18}\) 未満の整数 \(X\) があります。はじめ、Alice のみ \(X\) を知っています。

ゲームの目的は Bob が \(X\) を特定することです。

そのために、Alice は Bob へ、長さが \(1\) 以上の \(01\) 列 \(S\) を \(1\) つ送信することができます。

Bob が、送信された \(S\) を見て、\(X\) を当てることができたらゲームは成功となります。このとき、\(S\) が短いほど良い評価が得られます。

できるだけ短い \(S\) でゲームを成功させるような \(2\) つのプログラム Alice, Bob を作成してください。

すべてのゲームにおいて、\(S\) の長さが \(59\) 以下であるとき、満点が得られます。

Interaction

この問題はインタラクティブ問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが、ジャッジプログラムを介してゲームを行います。

あなたのプログラムは、最初に以下の形式で入力を受け取ってください。

	\(\mathrm{Player}\)
	\(T\)

ここで、\(\mathrm{Player}\) は文字列 Alice または文字列 Bob であり、\(T\) は \(1\) 以上 \(100\) 以下の整数です。

その後、各ゲームについて以下に示す入出力を行ってください。

ゲームの開始時、Alice は、以下の形式で入力を受け取ってください。

\(X\)

ここで、\(X\) は \(0\) 以上 \(10^{18}\) 未満の整数です。

Alice は、Bob に送信する \(01\) 列 \(S\) を以下の形式で出力してください。

\(S\)

ここで、\(S\) は、\(0,1\) からなる長さが \(1\) 以上 \(200\) 以下の文字列でなければなりません。

Bob は、Alice から送信された \(01\) 列 \(S\) を以下の形式で受け取ってください。

\(S\)

ここで、\(S\) は、\(0,1\) からなる長さが \(1\) 以上 \(200\) 以下の文字列です。

Bob は、\(S\) を受け取った後に \(X\) を特定し、以下の形式で出力してください。

\(X\)

ここで、\(X\) は、\(0\) 以上 \(10^{18}\) 未満の整数でなければなりません。

Alice として振る舞うプログラムは、\(T\) 回目のゲームにおいて \(S\) を出力した後は、ただちにプログラムを終了してください。 Bob として振る舞うプログラムは、\(T\) 回目のゲームにおいて \(X\) を出力した後は、ただちにプログラムを終了してください。

出力形式にミスがあった場合や前回のゲームに失敗した場合、それ以降の \(X\) や \(S\) は与えられず、文字列 -1 が標準入力から与えられます。この場合、ただちにプログラムを終了してください。

Scoring

ある \(1\) 回のゲームにおける、Alice が送信した \(S\) の長さを \(L'\) とします。この問題のすべてのゲームにわたる \(L'\) の最大値を \(L\) として、

\(L \leq 59\) のとき、\(100\) 点
\(59 \lt L \leq 200\) のとき、\(\displaystyle \left\lfloor10 + 70 \log_2\left(\frac{280}{L+80}\right)\right\rfloor\) 点
\(200 \lt L\) のとき、\(0\) 点

が与えられます。

この問題では、獲得した点数が最後に増加した時刻を回答時間とします。

Note

出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果は不定です。
ジャッジプログラムと、Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが同時に実行されます。実行時間・使用メモリはこれらの合計で計測されるため、実行時間・使用メモリには余裕を持ってください。

入出力例

Alice の入力	Alice の出力	Bob の入力	Bob の出力	説明
Alice		Bob		はじめに \(\mathrm{Player}\) と \(T\) が標準入力から与えられます。
3		3
10				Alice に対して \(X\) が標準入力から与えられます。
	1100			Alice が、Bob へ \(S\) を送信します。
		1100		Bob に、Alice が送信した \(S\) が与えられます。
			10	Bob が、\(X = 10\) であると解答します。
				Alice が受け取った \(X\) と一致しているため、ゲームは成功となります。
100				\(2\) 回目のゲームが始まります。
				Alice に対して \(X\) が標準入力から与えられます。
	1010			Alice が、Bob へ \(S\) を送信します。
		1010		Bob に、Alice が送信した \(S\) が与えられます。
			0	Bob が、\(X = 0\) であると解答します。
				Alice が受け取った \(X\) と一致していないため、ゲームは失敗となります。
-1		-1		ゲームに失敗したため、Alice と Bob の両方に -1 が与えられます。
				以降のゲームは行われないため、プログラムを終了させる必要があります。