問題一覧 > 通常問題

No.1152 10億ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : / 解いたユーザー数 29
作問者 : Kiri8128Kiri8128 / テスター : 37zigen37zigen
4 ProblemId : 4580 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-06 23:09:29

問題文

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

10億ゲームをしましょう！10億ゲームとは、10億の正の約数からなる集合の上で行う鬼ごっこです。
あなたは鬼です。35ターン以内に相手のきり君を捕まえてゲームに勝ってください！

ゲームの進行とルールは以下のとおりです。

ゲームの進行とルール

ゲームは次のように進行します。
  • 最初に、あなたときり君に整数が与えられます。
  • あなたから始めて、交互に、自身の整数を変化させていきます。変化のさせ方については次のセクションを見てください。
  • どこかの時点であなたの整数ときり君の整数が一致したら、あなたはきり君を捕まえることができます。その時点で鬼であるあなたの勝ちとなり、ゲームは終了します。どちらの順番で一致してもOKです。
  • 35ターン以内に捕まえられなければあなたの負けです。なお、この問題では、あなたときり君が1回ずつ整数を変化させるまでを1ターンと数えます。

整数の変化のさせ方

数字を変化させるときは、現在の自分の整数を $x$ として、次の条件（★）を満たす $i\ (1\le i\le 4)$ を1つ選び、自分の整数を $f_i(x)$ に変化させます。

　　条件（★）：$f_i(x)$ は $x$ と等しくない正の整数であり、かつ $10^9$ の約数である。

ただし $f_i(x)\ (1\le i \le 4)$ は次のように定義されます。 $$\left\{ \begin{eqnarray} f_1(x) &=& \displaystyle\frac{x}{2} \\ f_2(x) &=& \displaystyle\frac{x}{5} \\ f_3(x) &=& \min(2x,\ 10^9) \\ f_4(x) &=& \min(5x,\ 10^9) \end{eqnarray}\right. $$

入出力

最初に、あなたの最初の整数 $x_1$ と、きり君の最初の整数 $x_2$ が空白区切りで与えられます。 
$x_1\ x_2$

$x_1$ と $x_2$ は互いに異なる正の整数であり、いずれも $10^9$ の約数であることが保証されます。


あなたの順番では、変化させた後のあなたの整数 $x_1$ を1行に出力してください。 
$x_1$

きり君の順番では、変化させた後のきり君の整数 $x_2$ が1行で与えられます。 
$x_2$

なおこの問題の制約下では、必ず勝つ方法が存在することが示せます。

注意点

  • 出力のたびに標準出力を Flush させてください。
  • ゲームが終了した場合は、その時点でプログラムを終了させる必要があることに注意してください。 あなたの順番で終了した場合はあなたの出力時に、きり君の順番で終了した場合はきり君からの整数を受け取ったときに、 ただちにプログラムを終了させる必要があります。
  • 35ターンが終わってもまだゲームが終了していなければ、あなたの負けです。その時点でプログラムを終了させてください。
  • 上記が守られない場合のジャッジは不定です（ TLE や RE になることがあります）。

サンプル

以下は説明用の例です。実際のテストケースにこれと同じ挙動をするケースがあることは保証されません。

「入力」欄と「出力」欄は時系列順に並んでいます。 $i=1,\ 2,\ \cdots$ の順に、入力欄と出力欄の $i$ 行目のどちらか（空行でない方）が実行されます。 （各 $i$ について、 $i$ 行目には「入力」欄と「出力」欄のどちらかが空行になっています。 空行は行番号を合わせるためのもので、実際に空行の入力が与えられたり空行の出力を求められたりするものではありません。）

サンプル1
入力
1 4

2
出力

2

最初に、あなたの最初の整数1ときり君の最初の整数4が与えられます（「入力」の1行目）。

あなたは、整数を2または5に変化させることができます。 （問題文中の $i=3$ および $i=4$ を選んだことに対応します。 $i=1$ および $i=2$ は条件（★）を満たさないため選べないことに注意してください。）
あなたは整数を2に変化させました（「出力」の2行目）。

きり君は整数を2、8、20に変化させることができます。 （問題文中の $i=1$ 、 $i=3$ 、 $i=4$ を選んだことに対応します。 $i=2$ は条件（★）を満たさないため選べないことに注意してください。）
きり君は整数を2に変化させました（「入力」の3行目）。

この時点であなたの整数ときり君の整数が一致したためあなたの勝ちです。
きり君の順番で終了した場合は、きり君の最後の整数（この場合は2）を受け取った時点でただちにプログラムを終了させてください。

サンプル2
入力
1000000000 500000000

出力

500000000

あなたの最初の整数は $10^9$ であり、 $f_1(10^9) = 5 \times 10^8$ または $f_2(10^9) = 2 \times 10^8$ に変化させることができます。 $f_3(10^9) = f_4(10^9) = 10^9$ ですが、元の整数と一致するものには変化させることができないことに注意してください。
あなたの順番で終了した場合は、あなたの整数の出力後、ただちにプログラムを終了させてください。

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