No.1590 Random Shopping
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 39
作問者 : e869120 / テスター : hirakich1000000007
タグ : / 解いたユーザー数 39
作問者 : e869120 / テスター : hirakich1000000007
問題文最終更新日: 2021-07-08 21:59:39
問題文
yuki 商店では今後 $N$ 日間にわたって商品が売られます。$i$ 日目の朝 $(1 \leq i \leq N)$ には新たに $A_i$ 円の商品が追加され、売られるまで残り続けます。
これから $1$ 日当たり $1$ 人の客が来ることが予定されています。$i$ 日目の夕方 $(1 \leq i \leq N)$ に来る客の 裕福さ は $R_i$ です。また、すべての客は $50\%$ の確率で「今残っている中で最も安い商品」を買い、$50\%$ の確率で商品を買わずに帰ります。
買い物の 満足度 は、すべての客における「裕福さ $\times$ 買った商品の値段」の総和です。ただし商品を買わずに帰った場合、その人の満足度は $0$ です。満足度の期待値を求めてください。
入力
$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $R_1$ $R_2$ $\cdots$ $R_N$
出力
満足度の期待値を出力してください。絶対誤差または相対誤差が $10^{-6}$ 以下の場合、正答とみなされます。
制約
- $1 \leq N \leq 500$
- $1 \leq A_i \leq 1000$
- $1 \leq R_i \leq 1000$
- 入力はすべて整数
サンプル
サンプル1
入力
2 4 6 9 3
出力
25.5
この入力例では、以下の $4$ 通りの事象が等確率で起こります:
- 誰も商品を買わない:満足度は $0$
- $1$ 日目に来る客が商品を買う:満足度は $9 \times 4 = 36$
- $2$ 日目に来る客が商品を買う:満足度は $3 \times 4 = 12$
- $1, 2$ 日目に来る客が商品を買う:満足度は $9 \times 4 + 3 \times 6 = 54$
サンプル2
入力
4 1 1 1 1 1 1 1 1
出力
2.0
サンプル3
入力
8 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
出力
50.75
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。