AT_past202303_k 金貨と袋のゲーム

高橋君と青木君が $ 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 $ の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ t $ $ p $ $ a_1 $ $ \ldots $ $ a_N $

答えを出力せよ。解との絶対誤差または相対誤差が $ 10^{−6} $ 以下であれば正解として扱われる。

### Sample Explanation 1 高橋君は以下のようにすることで獲得する金貨の総和の期待値が最大となります。 - $ 1 $ 番目のラウンドでは袋に何も入れない - $ 2 $ 番目のラウンドでは( $ 1 $ 番目のラウンドでペナルティが与えられなかった場合)袋に規定の枚数の金貨を入れる - $ 3 $ 番目のラウンドでは袋に何も入れない ### Sample Explanation 2 この入力に対する答えは $ 570.9 $ です。出力はこの値に一致していませんが、誤差が十分に小さいため正解として扱われます。 ### 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 $ - 入力はすべて整数