/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
高橋君は、折れ線グラフを描く次のような宿題を先生から与えられました。
- N 個の非負整数 A_1, A_2, \ldots, A_N が与えられる。ただし、A_1 = A_N = 0 が成り立つ。
- i = 1, 2, \ldots, N について、二次元平面上の座標 (i, A_i) に点 P_i を打つ。
- i = 1, 2, \ldots, N-1 について、点 P_i と点 P_{i+1} を結ぶ線分を描く。
高橋君は宿題を早く済ませたいので、A_1, A_2, \ldots, A_N の値をこっそり変更して、 描く線分の長さの総和を小さくしようと思います。
しかし、こっそり値を変更したことを先生に気づかれないためには、 A_1, A_2, \ldots, A_N の変更後の値をそれぞれ B_1, B_2, \ldots, B_N とするとき、 以下の条件をすべて満たす必要があります。
- B_1, B_2, \ldots, B_N はすべて非負整数である。
- A_1 と A_N の値は変更してはならない。すなわち、B_1 = B_N = 0 が成り立つ。
- \sum_{i=1}^{N} A_i = \sum_{i=1}^{N} B_i
高橋君が先生に気づかれないように A_1, A_2, \ldots, A_N の値を適切に変更するとき、 高橋君が描く線分の長さの総和の最小値を求めてください。
制約
- 2 \leq N \leq 100
- 0 \leq A_i \leq 100
- A_1 = A_N = 0
- \sum_{i=1}^N A_i \leq 100
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
想定解答との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。
入力例 1
4 0 3 0 0
出力例 1
5.0644951022459797
高橋君は、A_2 を 1 に、A_3 を 2 に変更することで、線分の長さの総和を最小にできます。
入力例 2
7 0 1 2 3 4 5 0
出力例 2
10.3245553203367599
Score : 6 points
Warning
Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Takahashi's teacher has given Takahashi homework that required him to draw a polyline as follows.
- Given are N positive integers A_1, A_2, \ldots, A_N, where A_1 = A_N = 0.
- For each i = 1, 2, \ldots, N, plot a point P_i at the coordinates (i, A_i) in a two-dimensional plane.
- For each i = 1, 2, \ldots, N-1, draw a segment connecting P_i and P_{i+1}.
To get it done early, Takahashi is planning to secretly modify the values of A_1, A_2, \ldots, A_N to shorten the total length of segments to draw.
However, in order to keep this secret modification from being noticed by his teacher, all of the following conditions must hold, where B_1, B_2, \ldots, B_N are the new values for A_1, A_2, \ldots, A_N after modification, respectively.
- B_1, B_2, \ldots, B_N are all non-negative integers.
- The values of A_1 and A_N cannot be modified, that is, B_1 = B_N = 0.
- \sum_{i=1}^{N} A_i = \sum_{i=1}^{N} B_i.
Find the minimum possible total length of segments to draw when Takahashi modifies the values of A_1, A_2, \ldots, A_N so that his teacher will not notice it.
Constraints
- 2 \leq N \leq 100
- 0 \leq A_i \leq 100
- A_1 = A_N = 0
- \sum_{i=1}^N A_i \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
It will be considered as correct when its absolute or relative error from our answer is at most 10^{-5}.
Sample Input 1
4 0 3 0 0
Sample Output 1
5.0644951022459797
Takahashi can minimize the total length of segments to draw by changing A_2 to 1 and A_3 to 2.
Sample Input 2
7 0 1 2 3 4 5 0
Sample Output 2
10.3245553203367599