AlgosiaとBajtekは非常に珍しい状況に置かれています。二人はそれぞれ長さ $n$ の独自のバイナリ文字列を持っています。彼らはこれらの文字列をできるだけ早く交換したいと考えています。
状況を難しくしているのは、彼らが現在「じゃんけん」の大会に参加しているという事実です。この大会は最近、技術的な革命を経験しました。参加者間のいかなる通信の試みも回避し、選手の戦略のランダム性に完全に集中するために、主催者は参加者を互いに完全に隔離し、彼らの間にコンピュータシステムを設置することにしました。各参加者は自分の手を宣言し、その後にのみラウンドの結果が明らかになります。
じゃんけんの試合ルールは以下の通りです。
- 試合は複数のラウンドで構成されます。
- 1ラウンドにつき、各プレイヤーは「パー」「グー」「チョキ」の3つのシンボルのうち1つを選択します。
- 次に、これらのシンボルが比較されます。プレイヤーが同じシンボルを選択した場合、そのラウンドは引き分けとなり、誰もポイントを獲得しません。それ以外の場合、より強いシンボルを出した人が1ポイントを獲得します（パーはグーに勝ち、グーはチョキに勝ち、チョキはパーに勝ちます）。
- 相手より2ポイント先取したプレイヤーが試合に勝利します。
- どちらかのプレイヤーが試合に勝利するまでラウンドが続きます。
AlgosiaとBajtekは、試合が終わる前に互いの文字列を知りたいと考えています。また、観客やファンの忍耐を試さないよう、できるだけ少ないラウンド数でプレイしたいとも考えています。彼らを助けるプログラムを作成してください。この問題を $t$ 個の独立したテストケースについて解く必要があります。
インタラクション
これはインタラクティブな問題です。あなたのプログラムは2つのコピーとして実行されます。1つはAlgosia用、もう1つはBajtek用です。各実行の入力の最初の行には、そのプログラムのコピーがどちらの役割を担当するかを示す文字列 Algosia または Bajtek が与えられます。
入力形式は両者で同一です。入力の最初の行には Algosia または Bajtek という文字列が含まれます。2行目には、AlgosiaとBajtekが互いに送信したいバイナリ文字列の長さ $n$ ($1 \le n \le 5000$) とテストケースの数 $t$ ($1 \le t \le 5$) が含まれます。その後、$t$ 回のプログラム間のインタラクションが行われます。
各テストケースの最初の行で、両方のプログラムは $0$ と $1$ のみからなる長さ $n$ の文字列を受け取ります。自分の文字列を読み込んだ後、AlgosiaとBajtekはゲームを開始します。1ラウンドの間、プレイヤーはまず自分の手（$c \in \{P, K, N\}$ のいずれか1文字）を含む行を出力し、次に相手プレイヤーの手を示す文字を同じ形式で入力から読み取ります。1つのテストケースにおける最大ラウンド数は20000です。この制限を超えると「不正解」という判定になります。
テストケースを終了するには、文字 ! (感嘆符)、スペース、それに続く $0$ と $1$ のみからなる長さ $n$ の文字列を出力する必要があります。Algosiaの場合はBajtekの文字列を、Bajtekの場合はAlgosiaの文字列を出力してください。結果を出力した後、プログラムは直ちに次のテストケースに進む（つまり、渡すべき文字列を含む行を読み込む）か、最後のテストケースであれば終了する必要があります。
回答を出力した後、cout.flush() や fflush(stdout) を呼び出すなどして、出力バッファをフラッシュしてください。
入出力例
| インタラクターからAlgosiaへ | Algosiaからインタラクターへ | インタラクターからBajtekへ | Bajtekからインタラクターへ | 注記 |
|---|---|---|---|---|
Algosia |
Bajtek |
インタラクターがAlgosiaとBajtekのプログラムに役割を伝えます。 | ||
5 2 |
5 2 |
二人はテストケースが2つあり、各文字列の長さが5であることを知ります。 | ||
10010 |
00001 |
AlgosiaとBajtekは自分の文字列を知ります。例えばBajtekはAlgosiaに4つの0と1つの1を渡す必要があります。 | ||
P |
K |
ゲーム開始。第1ラウンドでAlgosiaはパー、Bajtekはグーを出しました。Algosiaが1ポイント獲得！ | ||
K |
P |
二人は相手が出した手を知ります。 | ||
P |
P |
Algosiaはここで勝つと試合が終わってしまうため、勝てないことを知っています。Bajtekを助けるために再びパーを出します。Bajtekは実際に何が起きているかを察し、同じくパーを出しました。Algosiaは依然として1ポイントリードしています。 | ||
P |
P |
二人は相手の手を知り、それぞれ推測する時が来たと判断します。 | ||
! 00001 |
! 10010 |
これが最初のテストケースの正しい回答です。 | ||
00010 |
10001 |
インタラクターが各プレイヤーに渡すべき文字列を与えます。 | ||
P |
K |
Algosiaがポイントを獲得！ただし、各テストケースでポイントはリセットされるため、これでゲーム終了ではありません。 | ||
K |
P |
二人は相手の手を知ります。 | ||
! 10001 |
! 00010 |
この説明を短くするため（およびAlgosiaが勝つリスクを避けるため）、彼らは推測することにしました。審査員は参加者に対し、推測する前に少し多くの情報を伝えることを推奨しています。 |
注記
- 上記のインタラクションは最初のテストケース（名前は0a）に対応しています。
- 他のすべてのテスト（2番目のテストケース0bを含む）でも $t = 5, n = 5000$ となります。
- ラウンド終了後にどちらかのプレイヤーが相手より2ポイント多く持っている場合、プログラムは直ちに「不正解」という判定で終了します。
- 両方のプログラムは同時に開始されます。プログラムの実行時間は、インタラクターの開始から終了までの実時間として測定されます。
- リード（ポイント差）はテストケース間で引き継がれません。各テストケースの開始時に、両プレイヤーは0ポイントから開始します（前のテストケースの結果に関係なく）。
小課題
テストセットは1つのグループで構成され、最大10ポイントを獲得できます。$m$ を単一のテストにおけるすべてのテストケースを通じた最大ラウンド数とします。テストのスコアは以下のルールに従って決定されます。
| $m \le$ | スコア |
|---|---|
| 20000 | 1 |
| 16250 | 2 |
| 10000 | 3 |
| 8750 | 4 |
| 6250 | 5 |
| 5500 | 6 |
| 5250 | 7 |
| 5125 | 8 |
| 5050 | 9 |
| 5000 | 10 |
提出の最終スコアは、すべてのテストにおける最小スコアとなります。
実装の詳細
「ファイル」セクションでインタラクター pknsoc.cpp が利用可能です。これはSIO2での提出チェックに使用されるインタラクターと同一です。以下のコマンドで実行してください。
python3 pknrun.py [rozwiazanie] < [test] > [wyjscie]
ここで、pknsoc.cpp と oi.h は同じフォルダにある必要があります。インタラクターが入力を受け取る形式は、pknsoc.cpp ファイル内のコメントに記載されています。
フェアプレイの原則
ゲームの進行以外の方法（例：一方のプログラムが遅延して手を送信し、もう一方が時計を読み取るなど）によるプログラム間の通信は禁止されています。審査員がプログラム間で不正な通信の試みを確認した場合、提出が削除される可能性があり、悪質な場合は大会全体からの失格処分が下される可能性があります。