/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
0 以上 M 未満の N 個の実数 x_1,\ldots,x_N があります。
これら N 個のうち、値が k 以上 k+1 未満であるようなものが C_k 個あることがわかっています (k=0,1,\ldots,M-1)。
あなたは、x_1,\ldots,x_N の中央値と平均値の差の絶対値がどのくらい小さくなるか気になりました。
「x_1,\ldots,x_N の中央値と平均値の差の絶対値は b 未満にならない」と言えるような最大の b を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq C_k
- C_0+\ldots+C_{M-1}=N
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M
C_0 C_1 \ldots C_{M-1}
出力
答えを出力せよ。
なお、真の解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
3 3 0 1 2
出力例 1
0.0
例えば x_1=1.5, x_2=2, x_3=2.5 のとき、これらの中央値と平均値はともに 2 になり、差の絶対値は 0 となります。
絶対値が 0 未満になることはないので、「中央値と平均値の差の絶対値は b 未満にならない」と言えるような最大の b は 0 となります。
入力例 2
4 5 2 1 0 0 1
出力例 2
0.25
例えば x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100} のとき、これらの中央値は 1.5-2\times 10^{-100}、平均値は 1.75-10^{-100} となり、差の絶対値は 0.25+10^{-100} となります。
このように中央値と平均値の差の絶対値として 0.25 よりわずかに大きな値はありえますが、0.25 未満にはならないことが証明できます。よって答えは 0.25 となります。
入力例 3
10 10 1 0 0 0 0 0 0 0 0 9
出力例 3
0.4
真の解との絶対誤差または相対誤差が 10^{-6} 以下であれば正解となります。
Problem Statement
There are N real numbers x_1,\ldots,x_N between 0 (inclusive) and M (exclusive).
Among these N numbers, it is known that there are C_k numbers between k (inclusive) and k+1 (exclusive) for k=0,1,\ldots,M-1.
You are curious about how small the absolute difference between the median and the mean of x_1,\ldots,x_N can be.
Find the largest b such that the absolute difference between the median and the mean of x_1,\ldots,x_N cannot be smaller than b.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq C_k
- C_0+\ldots+C_{M-1}=N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
C_0 C_1 \ldots C_{M-1}
Output
Print the answer.
Your output will be considered correct if the absolute or relative error from the true answer is at most 10^{-6}.
Sample Input 1
3 3 0 1 2
Sample Output 1
0.0
For example, when x_1=1.5, x_2=2, x_3=2.5, the median and the mean of these numbers are both 2, and the absolute difference is 0.
Since the absolute difference cannot be smaller than 0, the largest b such that the absolute difference between the median and the mean cannot be smaller than b is 0.
Sample Input 2
4 5 2 1 0 0 1
Sample Output 2
0.25
For example, when x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100}, the median is 1.5-2\times 10^{-100}, the mean is 1.75-10^{-100}, and the absolute difference is 0.25+10^{-100}.
As seen here, the absolute difference between the median and the mean can be slightly larger than 0.25, but we can prove that it cannot be smaller than 0.25. Therefore, the answer is 0.25.
Sample Input 3
10 10 1 0 0 0 0 0 0 0 0 9
Sample Output 3
0.4
Your output will be considered correct if the absolute or relative error from the true answer is at most 10^{-6}.