問題一覧 > 通常問題

No.2819 Binary Binary-Operator

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 85
作問者 : 🦠みどりむし / テスター : FplusFplusF viral8 achapi 👑 AngrySadEight
11 ProblemId : 10948 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-27 10:25:25

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

問題文

B{0,1}\mathbb{B} \coloneqq \{\, 0, 1 \,\} 上の二項演算  ⁣:B×BB\otimes \colon \mathbb{B} \times \mathbb{B} \to \mathbb{B} は以下をすべて満たします:

  • 00=P0,00 \otimes 0 = P_{0, 0}
  • 01=P0,10 \otimes 1 = P_{0, 1}
  • 10=P1,01 \otimes 0 = P_{1, 0}
  • 11=P1,11 \otimes 1 = P_{1, 1}
ただし、44P0,0,P0,1,P1,0,P1,1(B)P_{0, 0}, P_{0, 1}, P_{1, 0}, P_{1, 1} \scriptsize \; (\in \mathbb{B}) はいずれも隠されており、あなたには与えられません。

あなたは、ジャッジプログラムに対して以下の質問を ちょうど 1\bold 1 行うことができます:

  • はじめに、以下をすべて満たすような長さ nn の列 v=(v1,v2,,vn)v = (v_1, v_2, \dots, v_n) を自由に選ぶ:
    • 3n<256\bold{3} \leq n < 256
    • {v1,v2,,vn}B\{\, v_1, v_2, \dots, v_n \,\} \subset \mathbb{B}
  • その後、(((v1v2)v3))vn( \cdots ((v_1 \otimes v_2) \otimes v_3) \otimes \cdots) \otimes v_n の値を尋ねる。

入力より与えられる {X,Y}B\{\, X ,Y \,\} \subset \mathbb{B} なる X,YX, Y に対して XYX \otimes Y の値を求めてください。

入出力

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

はじめに、ジャッジプログラムが標準入力より以下の形式で X,YX, Y を与える:

XYX \enspace Y

続いて、列 vv とその長さ nn を以下の形式で標準出力へ出力せよ:

nn
v1v2vnv_1 \enspace v_2 \enspace \dots \enspace v_n

質問に応じて、それに対する答えをジャッジプログラムが標準入力より以下の形式で与える:

tt
ここで tt(((v1v2)v3))vn( \cdots ((v_1 \otimes v_2) \otimes v_3) \otimes \cdots) \otimes v_n の値である。

最後に、求めた XYX \otimes Y の値を標準出力へ一行に出力し、プログラムを終了せよ。

注意点
  • 出力を行うたびに、末尾に改行を入れて標準出力を flush せよ。
  • 要件を満たさない出力を行った場合のジャッジ結果は不定である。余分な空白や改行を出力することも該当する。
  • インタラクションの終了後は直ちにプログラムを終了せよ。

制約

  • {P0,0,P0,1,P1,0,P1,1}B\{\, P_{0, 0}, P_{0, 1}, P_{1, 0}, P_{1, 1} \,\} \subset \mathbb{B}
  • {X,Y}B\{\, X, Y \,\} \subset \mathbb{B}
  • P0,0,P0,1,P1,0,P1,1P_{0, 0}, P_{0, 1}, P_{1, 0}, P_{1, 1} の値は各テストケースごとに固定である

サンプル

以下は (P0,0,P0,1,P1,0,P1,1)=(1,0,1,0)(P_{0, 0}, P_{0, 1}, P_{1, 0}, P_{1, 1}) = (1, 0, 1, 0) であった場合の入出力例です:

入力 出力 意味 備考
0 0 (X,Y)=(0,0)(X, Y) = (0, 0)
3
0 0 0
v=(v1,v2,v3)=(0,0,0)v = (v_1, v_2, v_3) = (0, 0, 0)
1 (v1v2)v3=(00)0=1   ()(v_1 \otimes v_2) \otimes v_3 = (0 \otimes 0) \otimes 0 = 1 \>\>\>\text{---}\> (\star) (00)0=P0,00=10=P1,0=1(0 \otimes 0) \otimes 0 = P_{0, 0} \otimes 0 = 1 \otimes 0 = P_{1, 0} = 1 である。
1 XY=00=1X \otimes Y = 0 \otimes 0 = 1 00=00 \otimes 0 = 0 を仮定すると (00)0=00=0(0 \otimes 0) \otimes 0 = 0 \otimes 0 = 0 であり ()(\star) に反する。
ゆえに 00=10 \otimes 0 = 1 とわかる。
すべてのテストケースについて、P0,0,P0,1,P1,0,P1,1,X,YP_{0, 0}, P_{0, 1}, P_{1, 0}, P_{1, 1}, X, Y の値はいずれも 00 または 11 であることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。