No.3519 A/B問題
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : / 解いたユーザー数 26
作問者 : 👑
p-adic
/ テスター :
👑
loop0919
タグ : / 解いたユーザー数 26
作問者 : 👑
問題文最終更新日: 2026-05-01 22:06:29
問題文
この問題はリアクティブ形式の(ジャッジ側のプログラムと対話的に実行する必要がある)問題です。
割り算大好きbotは割り算が大好きなbotです。
割り算大好きbotは非負整数 $A$ と正整数 $B$ を隠し持っており、$A$ を $B$ で割った分数 $A/B$ を超えない最大の整数 $\lfloor A/B \rfloor$ を知りたがっています。
そこで、最初に非負整数 $a$ を $A$ と定め、以下の一連のやり取り(以下、質問と呼ぶ)を $0$ 回以上 $1000$ 回以下の好きな回数行います。
- まずあなたが $10^{100}$ 以下の非負整数 $n, m$ を選び、$na$ と $mB$ の大小関係を尋ねる。
- 続いて割り算大好きbotが $na$ と $mB$ の大小関係をあなたに答える。
- 最後に $na \geq mB$ である時は $a$ を $na - mB$ に置き換えて更新する。
その後、$\lfloor A/B \rfloor$ を求めてください。
入出力
最初に質問を $0$ 回以上 $1000$ 回以下の好きな回数してください。質問は標準入出力を用いて以下の形式で行います:
- まず $10^{100}$ 以下の非負整数 $n, m$ を選び、
?と $n, m$ を半角空白区切りで $1$ 行で出力してください。 - 続いて $na > mB$ ならば
>、 $na = mB$ ならば=、 $na < mB$ ならば<が与えられます。
? $n$ $m$
次にあなたはこの問題に対する答えを標準出力に以下の形式で出力してください:
-
!と $\lfloor A/B \rfloor$ を半角空白区切りで $1$ 行で出力してください。
! $\lfloor A/B \rfloor$
最後に改行してください。
制約
入力では与えられませんが $A, B$ は以下の制約を満たします:
- 全ての質問の前に $A, B$ は固定されている。すなわち質問の前後で $A, B$ の値は変化しない。
- $A$ は $0 \leq A \leq 10^{100}$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^{100}$ を満たす整数である。
入力は以下の制約を満たします:
- $10^{100}$ 以下の任意の非負整数 $n, m$ に対し、$na$ と $mB$ の大小を尋ねた際の返答である入力は
>、=、<のいずれかの文字である。
注意
リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。
この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません:
- 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
- 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
- この問題に対する答えを出力した後はプログラムをすぐに終了させてください。
サンプル
以下は割り算大好きbotが $(A,B) = (70,9)$ を隠し持っている場合の対話の一例です。
最初は $a = A = 70$ です。
| 入力 | 出力 | 説明 |
|---|---|---|
? 13 100 |
あなたは $13a$ と $100B$ の大小関係を尋ねました。 | |
> |
割り算大好きbotは $13a = 910$ が $100B = 900$ より大きいと答えました。$13a \geq 100B$ なので $a$ を $13a - 100B = 910 - 900 = 10$ に置き換えて更新します。 | |
? 11 20 |
あなたは $11a$ と $20B$ の大小関係を尋ねました。 | |
< |
割り算大好きbotは $11a = 110$ が $20B = 180$ より小さいと答えました。$11a \geq 20B$ でないので $a$ を更新しません。 | |
? 9 10 |
あなたは $9a$ と $10B$ の大小関係を尋ねました。 | |
= |
割り算大好きbotは $9a = 90$ が $10B = 90$ と等しいと答えました。$9a \geq 10B$ なので $a$ を $9a - 10B = 90 - 90 = 0$ に置き換えて更新します。 | |
! 7 |
あなたは $\lfloor A/B \rfloor$ が $7$ であると答えました。これは正解です。 |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。