/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 575 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
k=1,2,\ldots,N について次の問題を解いてください。
- k\leq r\leq N をみたす整数 r を選んだ時、数列 A の k 項目から r 項目までの平均値としてあり得る最大値を求めよ。
ここで、数列 A の k 項目から r 項目までの平均値は \frac{1}{r-k+1}\displaystyle\sum_{i=k}^r A_i で定義される値である。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 行出力せよ。
i 行目 (1\leq i\leq N) には、k=i のときの問題の答えを出力せよ。
出力は、すべての行の出力について、その行の出力の真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
5 1 1 4 5 3
出力例 1
2.80000000 3.33333333 4.50000000 5.00000000 3.00000000
k=1 のときについて、r としてあり得るのは r=1,2,3,4,5 であり、それぞれの時の平均値は、
- \frac{1}{1}=1
- \frac{1}{2}(1+1)=1
- \frac{1}{3}(1+1+4)=2
- \frac{1}{4}(1+1+4+5)=2.75
- \frac{1}{5}(1+1+4+5+3)=2.8
となります。よって、r=5 のときが最大であり、k=1 のときの答えは 2.8 となります。
同様に k=2,3,4,5 のときはそれぞれ r=4,4,4,5 としたときが最大であり、その値は \frac{10}{3}=3.333\ldots, \frac{9}{2}=4.5, \frac{5}{1}=5, \frac{3}{1}=3 となります。
入力例 2
3 999999 1 1000000
出力例 2
999999.00000000 500000.50000000 1000000.00000000
Score: 575 points
Problem Statement
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
For each k=1,2,\ldots,N, solve the following problem:
- Find the maximum possible average value of the k-th to r-th terms of the sequence A when choosing an integer r such that k\leq r\leq N.
Here, the average value of the k-th to r-th term of the sequence A is defined as \frac{1}{r-k+1}\displaystyle\sum_{i=k}^r A_i.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print N lines.
The i-th line (1\leq i\leq N) should contain the answer to the problem for k=i.
Your output will be considered correct if, for every line, the absolute or relative error of the printed value from the true value is at most 10^{-6}.
Sample Input 1
5 1 1 4 5 3
Sample Output 1
2.80000000 3.33333333 4.50000000 5.00000000 3.00000000
For k=1, the possible choices for r are r=1,2,3,4,5, and the average value for each of them is:
- \frac{1}{1}=1
- \frac{1}{2}(1+1)=1
- \frac{1}{3}(1+1+4)=2
- \frac{1}{4}(1+1+4+5)=2.75
- \frac{1}{5}(1+1+4+5+3)=2.8
Thus, the maximum is achieved when r=5, and the answer for k=1 is 2.8.
Similarly, for k=2,3,4,5, the maximum is achieved when r=4,4,4,5, respectively, with the values of \frac{10}{3}=3.333\ldots, \frac{9}{2}=4.5, \frac{5}{1}=5, \frac{3}{1}=3.
Sample Input 2
3 999999 1 1000000
Sample Output 2
999999.00000000 500000.50000000 1000000.00000000