外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

W - Nyaometry Dash

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 650 点

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

わりとねこくんは、ねこ星で大流行中のゲーム「ニャオメタリーダッシュ」で遊んでいます。

ニャオメタリーダッシュのステージは NN 個の区間 1,2,…,N1, 2, \dots, N に分かれており、最初、区間 ii の難易度は DiD_i です。 わりとねこくんが難易度 XX の区間を 11 回プレイすると、成功率 (100−0.1X)%(100 - 0.1 X)\%(すなわち確率 1000−X1000\frac{1000 - X}{1000})で成功して次の区間へ進み、失敗率 0.1X%0.1 X\%(確率 X1000\frac{X}{1000})で失敗します。

わりとねこくんは、ステージに挑戦する前に最大 KK 回まで練習をすることができます。11 回の練習では任意の 11 つの区間を選び、その区間の難易度を 11 だけ減少させることができます。ただし、すでに難易度が 00 である区間を選んだ場合、難易度は 00 のまま変わりません。

ステージへの挑戦は区間 11 から始まり、区間 1,2,…,N1, 2, \dots, N をこの順番に連続で成功するとクリアとなります。途中で失敗した場合は、即座に区間 11 に戻されて再び区間 11 からやり直しになります。 また、成功・失敗にかかわらず、区間を 11 つプレイするごとに 11 単位時間がかかります。

適切に練習を行ったときに、ステージをクリアするまでにかかる時間の期待値の最小値を求めてください。 ここで、答えは 1010010^{100} 以下であることが保証されています。

制約

  • 1≤N≤5001 \le N \le 500
  • 0≤K≤100000 \le K \le 10000
  • 0≤Di≤7500 \le D_i \le 750 (1≤i≤N1 \le i \le N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

NN KK D1D_1 D2D_2 …\dots DND_N

出力

クリアまでにかかる時間の期待値の最小値を出力してください。 なお、出力された値と真の値との絶対誤差または相対誤差が 10−610^{-6} 以下であれば正解とみなされます。

入力例 1

2 100
500 600

出力例 1

6.0000000000

区間 22 に対して練習を 100100 回行うと、区間の難易度はそれぞれ 500,500500, 500(どちらも成功率 50%50\%)になります。 このとき、クリアまでにかかる時間の期待値はちょうど 66 となり、これが最小です。

入力例 2

3 0
200 500 750

出力例 2

22.0000000000

練習を行うことができず、それぞれの区間の成功率は 80%,50%,25%80\%, 50\%, 25\% となります。 区間 11 までを突破する期待時間は 1.251.25、区間 22 までは (1+1.25)/0.5=4.5(1 + 1.25) / 0.5 = 4.5、区間 33 まで(クリア)は (1+4.5)/0.25=22(1 + 4.5) / 0.25 = 22 となります。

入力例 3

2 500
500 500

出力例 3

2.9610124003

区間 11 を 8181 回、区間 22 を 419419 回練習して難易度をそれぞれ 419,81419, 81 にしたとき、期待値は 1581000533939≈2.9610124003\frac{1581000}{533939} \approx 2.9610124003 となり、これが最小です。

誤差ジャッジ:絶対誤差または相対誤差が10-6以下なら正解です。

参加受付は終了しました。