実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
0 でない整数 x_1, \ldots, x_N が与えられます.i,j,k を 1\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