問題一覧 > 通常問題

No.1816 MUL-DIV Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 139
作問者 : nok0nok0 / テスター : rianoriano
8 ProblemId : 7536 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-21 23:34:48

問題文

黒板に $N$ 個の整数 $A_1,A_2,\dots A_N $ が書いてあります。

黒板に書かれた整数を使って Alice と Bob がゲームをします。 Alice が先手で、黒板に書かれた整数が $1$ 個になるまで交互に以下の操作を行います。

  • Alice が行う操作

    • 黒板に書かれた整数を $2$ つ選ぶ(選んだ整数を $x$ と $y$ とする)。 $x$ と $y$ を黒板から消し、新たに $x\cdot y$ を黒板に書く。
  • Bob が行う操作

    • 黒板に書かれた整数を $2$ つ選ぶ(選んだ整数を $x$ と $y$ とする)。 $x$ と $y$ を黒板から消し、新たに $\lceil \frac{x}{y} \rceil$ を黒板に書く。

最終的に黒板に書かれている唯一の整数を $\mathrm{ans}$ とします。 Alice の目的は $\mathrm{ans}$ を最大化することで、 Bob の目的は $\mathrm{ans}$ を最小化することです。

両者が目的のために最善を尽くすとき、 $\mathrm{ans}$ を求めてください。

ただし実数 $a$ にたいし $\lceil a \rceil$ は $a$ 以上の最小の整数を表します。

制約

  • 入力は全て整数
  • $1 \le N\le 10^5$
  • $1 \le A_i \le 10^9$

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$\mathrm{ans}$ を出力してください。

サンプル

サンプル1
入力
2
3 5
出力
15

Alice は $3$ と $5$ を消して $3\cdot5 = 15$ を書きます。よって $\mathrm{ans}=15$ です。

サンプル2
入力
3
1 1 1
出力
1

Alice は $1$ と $1$ を消して $1\cdot1 = 1$ を書きます。Bob は $1$ と $1$ を消して $\lceil \frac{1}{1} \rceil=1$ を書きます。よって $\mathrm{ans}=1$ です。

サンプル3
入力
1
10
出力
10

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