/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
高橋君と青木君が N ラウンドからなるゲームをしています。 i=1,\ldots,N に対し、i 番目のラウンドでは以下の手順を上から順に行います。
- i \geq 2 かつ i-1 番目のラウンドで高橋君にペナルティが与えられていた場合、以降の手順を行わずに i 番目のラウンドを終了する。
- 高橋君に a_i 枚の金貨が配られる。
- 高橋君が以下のうち一方の行動を選ぶ。
- 袋に \left \lfloor \frac{a_i \times t}{100} \right \rfloor 枚の金貨を入れて青木君に示す。 (\lfloor x \rfloor は x を超えない最大の整数) ここで、\left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1 であることが保証される。
- 袋に何も入れずに青木君に示す。
- 青木君が 1 以上 100 以下の整数のうち 1 つを等確率で選び、x とする。
- x\leq p の場合、袋の中を確認する。もし袋に金貨が入っていなかった場合、高橋君に \left \lfloor \frac{a_i \times t}{100} \right \rfloor 枚の金貨を袋に入れさせた上で高橋君にペナルティを与える。
- x \gt p の場合、何もしない。
- このラウンドで配られた金貨のうち袋に入れられていない分を高橋君が獲得する。
なお、青木君は各ラウンドで独立に x を選びます。
高橋君は、 N ラウンド全体で獲得する金貨の枚数の総和の期待値 E が最大となるように各ラウンドでの行動を選びます。この時の E の値を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq t,p \leq 99
- 1 \leq a_i \leq 10^9
- \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N t p a_1 \ldots a_N
出力
答えを出力せよ。解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。
入力例 1
3 10 50 100 10 300
出力例 1
384.50000000000000000000
高橋君は以下のようにすることで獲得する金貨の総和の期待値が最大となります。
- 1 番目のラウンドでは袋に何も入れない
- 2 番目のラウンドでは(1 番目のラウンドでペナルティが与えられなかった場合)袋に規定の枚数の金貨を入れる
- 3 番目のラウンドでは袋に何も入れない
入力例 2
3 1 10 192 191 190
出力例 2
570.89999999999997726263
この入力に対する答えは 570.9 です。出力はこの値に一致していませんが、誤差が十分に小さいため正解として扱われます。
入力例 3
4 17 55 32 10 77 1000000000
出力例 3
906500100.00000000000000000000
Problem Statement
Takahashi and Aoki are playing a game with N rounds. For i=1,\ldots,N, the i-th round consists of the following steps in the order from top to bottom.
- If i \geq 2 and Takahashi received a penalty in the (i-1)-th round, the i-th round ends without performing the steps below.
- Takahashi is dealt a_i gold coins.
- Takahashi does one of the following actions.
- Put \left \lfloor \frac{a_i \times t}{100} \right \rfloor gold coins into a bag and show it to Aoki. (\lfloor x \rfloor is the greatest integer not exceeding x.) Here, it is guaranteed that \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1.
- Show an empty bag to Aoki.
- Aoki chooses an integer x between 1 and 100, inclusive, with equal probability.
- If x\leq p, he examines the bag. If it contains no gold coins, Takahashi puts \left \lfloor \frac{a_i \times t}{100} \right \rfloor gold coins into the bag and receives a penalty.
- If x \gt p, he does nothing.
- Takashi earns all gold coins dealt in this round that are not in the bag now.
Here, Aoki chooses x independently in each round.
Takahashi will make his choice in each round to maximize the expected value E of the total number of gold coins earned in all N rounds. Find this maximized value of E.
Constraints
- 1 \leq N \leq 100
- 1 \leq t,p \leq 99
- 1 \leq a_i \leq 10^9
- \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N t p a_1 \ldots a_N
Output
Print the answer. Your output is considered correct if its absolute or relative error from the true answer is at most 10^{−6}.
Sample Input 1
3 10 50 100 10 300
Sample Output 1
384.50000000000000000000
Here is a way for Takahashi to maximize the expected value of the total number of gold coins earned.
- In the first round, put nothing into the bag.
- In the second round, put the specified number of gold coins into the bag (if he did not receive a penalty in the first round).
- In the third round, put nothing into the bag.
Sample Input 2
3 1 10 192 191 190
Sample Output 2
570.89999999999997726263
The true answer to this input is 570.9. The above output is not identical to this value, but the error is small enough to be considered correct.
Sample Input 3
4 17 55 32 10 77 1000000000
Sample Output 3
906500100.00000000000000000000