No.2221 Set X
タグ : / 解いたユーザー数 58
作問者 :
stoq
/ テスター :
Shirotsume
misty1999
問題文
長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。