No.3246 80% Accuracy Calculator
タグ : / 解いたユーザー数 28
作問者 :


問題文
この問題はインタラクティブな問題(あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題)です.
$8$ 割の確率でしか計算に成功しない計算機で,計算を行う様子をシミュレーションしてみましょう.
ここに,$3$ 個の変数 $A, B, C$ があります.最初,変数 $A, B$ はそれぞれあらかじめジャッジシステムによって用意された正整数 $x, y$ で初期化されており,$C$ は $0$ で初期化されています.
ここで,$1 \leq x \leq 888, 1 \leq y \leq 888$ が成り立ちます.
あなたは,この変数に対して次に示す操作 1,操作 2 のどちらかを行うことができます.
- 操作 1 :変数 $A, B, C$ のうちどれかを $1$ つ選び,その値をジャッジシステムに問い合わせる.
- 問い合わせた変数の真の値が $z$ であるとき,ジャッジシステムは $80\%$ の確率で $z$ を返し,$20\%$ の確率で $1 \leq w \leq 8,888,888, \ w \neq z$ を満たす,ジャッジによって選択された整数 $w$ を返す($w$ の選び方はランダムとは限らない).
- 操作 2 :変数の足し算を行う.$3$ つの変数 $v_1, v_2, v_3$ をそれぞれ $A, B, C$ の中から(重複を許して)$1$ つずつ選び,ジャッジシステムに変数 $v_1$ の値と変数 $v_2$ の値の和(以降これを $s$ とします)を,変数 $v_3$ へ代入してもらう.
- ただし,$v_1 \neq v_3, v_2 \neq v_3$ を満たしていなければならない.また,操作の際に $s$ の値が $8,888,888$ を超えていてはならない.
- ジャッジシステムは,$80\%$ の確率で変数 $v_3$ の値を $s$ で置き換え,$20\%$ の確率で変数 $v_3$ の値を,ジャッジによって選択された $1 \leq w \leq 8,888,888, \ w \neq s$ を満たす整数 $w$ で置き換える($w$ の選び方はランダムとは限らない).
- このとき,変数 $v_1$ および $v_2$ の値は書き換わることなく,そのままである.
あなたの目標は,変数 $A, B, C$ のいずれかに,$x \times y$ の値が格納されている状態にすることです.
$8888$ 回以内の操作で,目標を達成してください.
なお,$x, y$ の値は対話の開始前に決定されます.
制約
- $1 \leq x, y \leq 888$
- $x, y$ は整数
入出力
この問題はインタラクティブな問題(あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う問題)です.
操作 1 を行う場合は,以下の形式で出力してください.ここで,$v$ は値を問い合わせたい変数の名前で,A
, B
, C
のいずれかで表されます.
? $v$
この質問への返答は,次の形式で標準入力から与えられます.
$z$
ここで,$z$ はジャッジシステムから返される質問の返答です(詳細は上記参照).
不正な質問をした場合や,操作回数の合計が $8888$ 回を超えている場合は,$z = -1$ が与えられます.この場合,既に不正解と判定されていますので,ただちにプログラムを終了してください.
操作 2 を行う場合は,以下の形式で出力してください.ここで,$v_1, v_2, v_3$ は足し算を行う変数の名前で,A
, B
, C
のいずれかで表されます.また,$v_1 \neq v_3, v_2 \neq v_3$ を満たすように選ぶ必要があります.
+ $v_1$ $v_2$ $v_3$
この質問への返答は,次の形式で標準入力から与えられます.
$z$
ここで,操作 2 が正常に行われた場合,$z=0$ が与えられます.($v_3$ の値が $s$ に書き変わったかどうかの情報は与えられないことに注意してください.)
不正な質問をした場合や,操作回数の合計が $8888$ 回を超えている場合は,$z = -1$ が与えられます.この場合,既に不正解と判定されていますので,ただちにプログラムを終了してください.
変数 $A, B, C$ のいずれかに $x \times y$ の値が格納されている状態になった場合,以下の形式でその旨を報告してください.その後,プログラムを終了してください.ここで,$v$ は $x \times y$ が格納されている変数の名前で,A
, B
, C
のいずれかで表されます.
! $v$
このとき,指定した変数の値が $x \times y$ であれば正解,そうでなければ不正解となります.
注意点
- 出力のたびに必ず標準出力を flush してください.そうしない場合,TLE になる可能性があります.
- 不正な出力が行われた場合,ジャッジの結果は不定です.
- $z=-1$ が入力として与えられた後に,プログラムをただちに終了しなかった場合,ジャッジの結果は不定です.
- $x \times y$ が格納されている変数を報告した後は,プログラムをただちに終了してください.そうしなかった場合,ジャッジの結果は不定です.
- $x \times y$ が格納されている変数を報告する出力は,質問回数に含まれません.
サンプル
以下は,$x = 2, y = 4$ である場合の,正解となる入出力例です.
なお,以下の「説明」欄では各変数の実際の値をもとに説明が行われていますが,実際にはこの値は直接的に確認できないことに注意してください.
入力 | 出力 | 説明 |
---|---|---|
? A |
変数 $A$ の値を尋ねます. | |
2 |
ジャッジシステムは $2$ を返しました.(このように,ジャッジシステムが尋ねられた変数の値を返すことは,$80\%$ の確率で起こります.) | |
? B |
変数 $B$ の値を尋ねます. | |
3123142 |
ジャッジシステムは $3123142$ を返しました.(このように,ジャッジシステムが尋ねられた変数の値以外を返すことは,$20\%$ の確率で起こります.) | |
+ A B C |
変数 $C$ に,変数 $A, B$ の値の和を代入する操作をしてもらいます. | |
0 |
操作 2 が正常に行われたため $0$ が返されましたが,実際に代入された値は $2 + 4 = 6$ ではなく,$1128089$ でした.これにより,$(A, B, C) = (2, 4, 1128089)$ となります.(このように,$2$ 変数の和とは異なる整数に書き変わることは,$20\%$ の確率で起こります.) | |
+ B B C |
変数 $C$ に,変数 $B, B$ の値の和を代入する操作をしてもらいます.$v_1=v_2$ であってもよいことに注意してください. | |
0 |
操作 2 が正常に行われたため $0$ が返され,実際に $4 + 4 = 8$ が代入されました.これにより,$(A, B, C) = (2, 4, 8)$ となります.(このように,$2$ 変数の和に書き変わることは,$80\%$ の確率で起こります.) | |
! C |
変数 $C$ の値が $x \times y = 2 \times 4 = 8$ であることを報告しました.実際に $C = 8$ なので,正解となります.ここでプログラムを終了してください. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。