リアクティブ問題です。
$1000$ ビットの非負整数が $200$ 個あり、$a_1, \ldots, a_{100}, b_1, \ldots, b_{100}$ とします。
アリスは $a_1, \ldots, a_{100}$ を確認し、$3000$ ビットのメモ $X$ をチャーリーのために残します。
ボブは $b_1, \ldots, b_{100}$ を確認し、$3000$ ビットのメモ $Y$ をチャーリーのために残します。
チャーリーはメモ $X, Y$ の情報をもとに、$100$ 個の質問に答えます。
$i$ 番目の質問は $1000$ ビットの非負整数 $c_i$ で表され、チャーリーは $a_{x_i}$ と $b_{y_i}$ のビットごとの排他的論理和が $c_i$ に等しくなるような $x_i, y_i$ を答えます。
$100$ 個の質問のうち、$95$ 個以上の質問に正答できる戦略を考えてください。
0
,1
からなる長さ $1000$ の文字列である。あなたのプログラムは $1$ つのテストケースに対して $3$ 回実行される。
$1$ 回目の実行では次の入力形式でアリスへの情報が与えられる。
Alice $a_1$ $a_2$ $\vdots$ $a_{100}$
$1$ 行目に必ず Alice
の文字列が与えられる。
この場合、入力を全て受け取った後 0
,1
からなる長さ $3000$ の文字列 $X$ を出力し、プログラムを即座に終了させなければならない。
$2$ 回目の実行では次の入力形式でボブへの情報が与えられる。
Bob $b_1$ $b_2$ $\vdots$ $b_{100}$
$1$ 行目に必ず Bob
の文字列が与えられる。
この場合、入力を全て受け取った後 0
,1
からなる長さ $3000$ の文字列 $Y$ を出力し、プログラムを即座に終了させなければならない。
$3$ 回目の実行では次の入力形式でチャーリーへの質問およびメモの情報が与えられる。
Charlie $X$ $Y$ $c_1$ $c_2$ $\vdots$ $c_{100}$
$1$ 行目に必ず Charlie
の文字列が与えられる。
入力を全て受け取った後 $1$ 以上 $100$ 以下の整数 $x_1, x_2, \ldots, x_{100}$ と $1$ 以上 $100$ 以下の整数 $y_1, y_2, \ldots, y_{100}$ を以下の形式で出力し、プログラムを即座に終了させなければならない。
$x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_{100}$ $y_{100}$
ジャッジは、$i = 1, 2, \ldots, 100$ について $a_{x_i}$ と $b_{y_i}$ のビットごとの排他的論理和が $c_i$ に一致するか調べ、一致数が $95$ 個以上であれば正答、そうでなければ誤答と判定する。
不正な値や不正な形式での出力があった場合にも誤答とする。
以下はビット数や非負整数の数、質問の数が異なるが、$a = (000, 011), b = (110, 111), c = (101, 100)$ としたときの対話例である。
解答プログラムの出力 | 解答プログラムへの入力 | 説明 |
---|---|---|
解答プログラム(アリス)が実行される | ||
Alice $000$ $011$ |
アリスは $a = (000, 011)$ の情報を得る | |
$0000110\ldots 0$ | アリスはメモ $X = 0000110\ldots 0$ を残す | |
解答プログラム(アリス)の実行が終了し、新たな解答プログラム(ボブ)が実行される | ||
Bob $110$ $111$ |
ボブは $b = (110, 111)$ の情報を得る | |
$1101110\ldots 0$ | ボブはメモ $Y = 1101110\ldots 0$ を残す | |
解答プログラム(ボブ)の実行が終了し、新たな解答プログラム(チャーリー)が実行される | ||
Charlie $0000110\ldots 0$ $1101110\ldots 0$ $101$ $100$ |
チャーリーは $X, Y$ の情報を得たあと、質問の情報 $c = (101, 100)$ を得る | |
$2$ $1$ $2$ $2$ |
チャーリーは $1$ つ目の質問に対して $(x_1, y_1) = (2, 1)$、$2$ つ目の質問に対して $(x_2, y_2) = (2, 2)$ と回答する |