問題一覧 > 通常問題

No.1590 Random Shopping

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 35
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007
1 ProblemId : 6695 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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$
したがって、求める満足度の期待値は $(0 + 36 + 12 + 54) \div 4 = 25.5$ となります。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。