No.2009 Drunkers' Contest
タグ : / 解いたユーザー数 41
作問者 :
Kiri8128
/ テスター :
MtSaka
問題文
きり君は飲酒プログラミングコンテストが大好きです。
飲酒プログラミングコンテストはお酒を飲みながら問題を解くコンテストです。
お酒を飲むと頭が冴えるため発想力は上がりますが、ミスが増えるため実装力が下がることが知られています。
このコンテストでは、問題 $1$ から問題 $N$ までの合計 $N$ 問が出題されます。
きり君はこれらの問題を問題 $1$ から順番に解きます。
各問題は発想パートと実装パートに分かれていて、お酒を累計で $x$ 飲んだ状態では
$i\ (1\le i\le N)$ 番目の問題にかかる時間は、発想パートが $\displaystyle\frac{A_i}{1+x}$ 分、実装パートが $B_i(1+x)$ 分です。
きり君は、 各問題を解き始める前に 好きなだけお酒を飲むことができます。
お酒を飲んでいない状態でコンテストを開始したとき、すべての問題を解き終えるまでに必要な時間の最小値を求めてください。
なおお酒を飲むのにかかる時間は無視できるものとします。
入力
$N$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$
入力はすべて整数
$1\le N\le 2\times 10^5$
$1\le A_i\le 10^9\ (1\le i\le N)$
$1\le B_i\le 10^9\ (1\le i\le N)$
出力
答えを出力してください。 正しい答えとの絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解とみなされます。 最後に改行してください。
サンプル
サンプル1
入力
2 2 18 3 2
出力
17
問題 1 を解き始める前にお酒は飲まず、問題 2 を解き始める前にお酒を $2$ （21:35 修正）だけ飲むのが最適です。 このとき問題 1 は発想パートは $2$ 、実装パートは $3$ で、合計 $5$ の時間がかかります。 問題 2 は発想パートは $18\div 3=6$ 、実装パートは $2\times 3 = 6$ で、合計 $12$ の時間がかかります。 合計すると $17$ の時間ですべての問題を解くことができます。 時間を $17$ より短くすることはできないので、 17 を出力すると正解になります。
サンプル2
入力
2 18 2 2 3
出力
20
サンプル 1 と問題の順番が逆になっています。 最初にお酒を $1$ （21:35 修正）だけ飲むのが最適です。 このとき問題 1 は発想パートは $18\div 2 = 9$ 、実装パートは $2\times 2 = 4$ で、合計 $13$ の時間がかかり、 問題 2 は発想パートは $2\div 2=1$ 、実装パートは $3\times 2 = 6$ で、合計 $7$ の時間がかかるので、かかる時間の合計は 20 です。 問題 2 を先に解くことはできないことに注意してください。
サンプル3
入力
1 2 1
出力
2.8284271247
問題 $1$ の開始前に $\sqrt2-1$ （21:35 修正）のお酒を飲むのが最適で、そのとき全体で $2\sqrt2$ の時間がかかります。 正しい答えとの絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解とみなされます。
サンプル4
入力
1 1 2
出力
3
お酒を全く飲まないのが最適です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。