問題一覧 > 通常問題

No.1152 One Billion Game

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : （AC するまで非表示） / 解いたユーザー数 34
作問者 : Kiri8128 / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 4580 / 自分の提出
問題文最終更新日: 2020-08-06 23:09:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 260 (Typical Game Contest) (順位表) の他の問題:

Problem Statement

This is an interactive problem.

Let's play the One Billion Game! The One Billion Game is a game of tag played on the set of positive divisors of one billion.
You are "it". Catch your opponent, Kiri-kun, within 35 turns and win the game!

The progression and rules of the game are as follows.

Progression and Rules of the Game

The game proceeds as follows.
  • First, you and Kiri-kun are each given an integer.
  • Starting with you, you take turns changing your own integer. See the next section for how an integer may be changed.
  • If at any point your integer and Kiri-kun's integer become equal, you can catch Kiri-kun. At that point you, being "it", win, and the game ends. It does not matter on whose move they become equal.
  • If you cannot catch him within 35 turns, you lose. Note that in this problem, one turn consists of you and Kiri-kun each changing their integer once.

How to Change an Integer

When changing a number, let $x$ be your current integer. Choose one $i\ (1\le i\le 4)$ satisfying the following condition (★), and change your integer to $f_i(x)$.

　　Condition (★): $f_i(x)$ is a positive integer not equal to $x$, and is a divisor of $10^9$.

Here, $f_i(x)\ (1\le i \le 4)$ is defined as follows. $$\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. $$

Input and Output

First, your initial integer $x_1$ and Kiri-kun's initial integer $x_2$ are given, separated by a space. 
$x_1\ x_2$

It is guaranteed that $x_1$ and $x_2$ are distinct positive integers and that both are divisors of $10^9$.


On your move, print your integer $x_1$ after the change on one line. 
$x_1$

On Kiri-kun's move, his integer $x_2$ after the change is given on one line. 
$x_2$

Under the constraints of this problem, it can be shown that a winning strategy always exists.

Notes

  • Flush standard output after each output.
  • Note that your program must terminate at the moment the game ends. If the game ends on your move, you must terminate the program immediately upon your output; if it ends on Kiri-kun's move, you must terminate the program immediately upon receiving the integer from Kiri-kun.
  • If the game has not ended after 35 turns have finished, you lose. Terminate your program at that point.
  • If the above is not followed, the judge result is undefined (it may be TLE, RE, etc.).

Sample

The following are examples for explanation. It is not guaranteed that the actual test cases include a case that behaves in the same way.

The "Input" and "Output" fields are arranged in chronological order. In the order $i=1,\ 2,\ \cdots$, line $i$ of either the input field or the output field (whichever is not blank) is executed. (For each $i$, line $i$ is blank in exactly one of the "Input" and "Output" fields. Blank lines are only there to align the line numbers; no blank line is actually given as input or required as output.)

Sample 1
Input
1 4

2
Output

2

First, your initial integer 1 and Kiri-kun's initial integer 4 are given (line 1 of "Input").

You can change your integer to 2 or 5. (These correspond to choosing $i=3$ and $i=4$ in the problem statement. Note that $i=1$ and $i=2$ cannot be chosen because they do not satisfy condition (★).)
You changed your integer to 2 (line 2 of "Output").

Kiri-kun can change his integer to 2, 8, or 20. (These correspond to choosing $i=1$, $i=3$, and $i=4$ in the problem statement. Note that $i=2$ cannot be chosen because it does not satisfy condition (★).)
Kiri-kun changed his integer to 2 (line 3 of "Input").

At this point your integer and Kiri-kun's integer are equal, so you win.
If the game ends on Kiri-kun's move, terminate your program immediately upon receiving Kiri-kun's last integer (2 in this case).

Sample 2
Input
1000000000 500000000

Output

500000000

Your initial integer is $10^9$, and you can change it to $f_1(10^9) = 5 \times 10^8$ or $f_2(10^9) = 2 \times 10^8$. Note that although $f_3(10^9) = f_4(10^9) = 10^9$, you cannot change your integer to a value equal to the original one.
If the game ends on your move, terminate your program immediately after printing your integer.

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