B - Sum-Product Ratio 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

0 でない整数 x_1, \ldots, x_N が与えられます.i,j,k1\leq i < j < k\leq N を満たす整数とするとき,\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる最小値と最大値を求めてください.

制約

  • 3\leq N\leq 2\times 10^5
  • -10^6\leq x_i \leq 10^6
  • x_i\neq 0

入力

入力は以下の形式で標準入力から与えられます.

N
x_1 \ldots x_N

出力

\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる最小値と最大値を,それぞれ 1 行目,2 行目に出力してください.

絶対誤差または相対誤差が 10^{-12} 以内であれば,正解と判定されます.


入力例 1

4
-2 -4 4 5

出力例 1

-0.175000000000000
-0.025000000000000

\dfrac{x_i+x_j+x_k}{x_ix_jx_k} としてありうる値は次の 4 通りです.

  • (i,j,k) = (1,2,3)\dfrac{(-2) + (-4) + 4}{(-2)\cdot (-4)\cdot 4} = -\dfrac{1}{16}
  • (i,j,k) = (1,2,4)\dfrac{(-2) + (-4) + 5}{(-2)\cdot (-4)\cdot 5} = -\dfrac{1}{40}
  • (i,j,k) = (1,3,4)\dfrac{(-2) + 4 + 5}{(-2)\cdot 4\cdot 5} = -\dfrac{7}{40}
  • (i,j,k) = (2,3,4)\dfrac{(-4) + 4 + 5}{(-4)\cdot 4\cdot 5} = -\dfrac{1}{16}

これらの最小値は -\dfrac{7}{40},最大値は -\dfrac{1}{40} です.


入力例 2

4
1 1 1 1

出力例 2

3.000000000000000
3.000000000000000

入力例 3

5
1 2 3 4 5

出力例 3

0.200000000000000
1.000000000000000

Score : 500 points

Problem Statement

You are given non-zero integers x_1, \ldots, x_N. Find the minimum and maximum values of \dfrac{x_i+x_j+x_k}{x_ix_jx_k} for integers i, j, k such that 1\leq i < j < k\leq N.

Constraints

  • 3\leq N\leq 2\times 10^5
  • -10^6\leq x_i \leq 10^6
  • x_i\neq 0

Input

The input is given from Standard Input in the following format:

N
x_1 \ldots x_N

Output

Print the minimum value of \dfrac{x_i+x_j+x_k}{x_ix_jx_k} in the first line and the maximum value in the second line.

Your output will be considered correct when the absolute or relative error is at most 10^{-12}.


Sample Input 1

4
-2 -4 4 5

Sample Output 1

-0.175000000000000
-0.025000000000000

\dfrac{x_i+x_j+x_k}{x_ix_jx_k} can take the following four values.

  • (i,j,k) = (1,2,3): \dfrac{(-2) + (-4) + 4}{(-2)\cdot (-4)\cdot 4} = -\dfrac{1}{16}.
  • (i,j,k) = (1,2,4): \dfrac{(-2) + (-4) + 5}{(-2)\cdot (-4)\cdot 5} = -\dfrac{1}{40}
  • (i,j,k) = (1,3,4): \dfrac{(-2) + 4 + 5}{(-2)\cdot 4\cdot 5} = -\dfrac{7}{40}
  • (i,j,k) = (2,3,4): \dfrac{(-4) + 4 + 5}{(-4)\cdot 4\cdot 5} = -\dfrac{1}{16}.

Among them, the minimum is -\dfrac{7}{40}, and the maximum is -\dfrac{1}{40}.


Sample Input 2

4
1 1 1 1

Sample Output 2

3.000000000000000
3.000000000000000

Sample Input 3

5
1 2 3 4 5

Sample Output 3

0.200000000000000
1.000000000000000