問題一覧 > 通常問題

No.2221 Set X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 : stoqstoq / テスター : ShirotsumeShirotsume misty1999misty1999
13 ProblemId : 8146 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-04 10:52:00

問題文

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)\ (A_1 < A_2 < \cdots < A_N)$ があります。

正の整数 $X$ に対し、$$f(X) := (X+1) \times \left| \left\{ \left \lfloor \frac{A_1}{X} \right \rfloor , \left \lfloor \frac{A_2}{X} \right \rfloor, \dots, \left \lfloor \frac{A_N}{X} \right \rfloor \right\} \right|$$ と定義します。 つまり $f(X)$ は $\displaystyle \left \lfloor \frac{A_1}{X} \right \rfloor , \left \lfloor \frac{A_2}{X} \right \rfloor, \dots, \left \lfloor \frac{A_N}{X} \right \rfloor$ の種類数と $X+1$ の積です。

$f(X)$ の最小値と、その最小値を達成する $X$ のうち最小のものを求めてください。

入力

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

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9$

出力

$f(X)$ を最小化する $X$ のうち最小のものを $X_{\min}$ として、以下の形式で出力してください。

$X_{\min}$
$f(X_{\min})$

サンプル

サンプル1
入力
4
0 1 2 3
出力
4
5

$f(4) = (4+1) \times \left| \left\{ 0 \right\} \right| = 5 \times 1 = 5$ です。

$f(X)$ をこれより小さくすることはできず、また $X < 4$ のとき $f(X) > 5$ であるため、$X=4$ および $f(X) = 5$ が解となります。

サンプル2
入力
6
3 4 5 6 7 8
出力
3
8

$f(3) = (3+1) \times \left| \left\{ 1,2 \right\} \right| = 4 \times 2 = 8$ です。

サンプル3
入力
8
0 1 2 6 7 9 10 11
出力
3
12

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