C - Devil's Contract
Benihuki
2
s
1024
MB
100
点
問題文
tRue くんは悪魔と $N$ 日間のゲームをします。はじめ、$p=0$ です。
$i$ 日目には、tRue くんは以下のどちらか一方の行動をとることができます。
- 獲得
$A_i$ 円受け取る。その後、確率 $p$ %で当たるくじを引き、当たればさらに $A_i$ 円を獲得し、$p=0$ になり、外れれば何も起きない。 - 貯金
$p=\min(p+B_i,100)$ と変更する。
tRue 君が得られる金額の最大化を目指して最適にゲームをするとき、最終的に得られる金額の期待値を求めてください。
制約
- $1 \leq N \leq 2\times 10^5$
- $1 \leq A_i \leq 10^9$
- $1\leq B_i \leq 100$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$
出力
答えを一行に出力せよ。
想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。
入力例 1
3
4 80
11 40
6 50
出力例 1
26.76
たとえば、$1$ 日目に貯金を選ぶと $p=80$ となり、このとき $2$ 日目に獲得を選ぶと、$80$% の確率で $22$ 円を、$20$% の確率で $11$ 円を得られます。
tRue くんが得られる金額の最大化を目指して最適に行動するとき、得られる金額の期待値は $26.76$ 円になることが示せるので、$26.76$ を出力します。
入力例 2
4
1000 1
1000 1
1000 1
1000 1
出力例 2
4000
毎日獲得を選ぶとよいです。
入力例 3
2
45 100
3633 45
出力例 3
7266