問題一覧 > 通常問題

No.2009 Drunkers' Contest

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : Kiri8128 / テスター : MtSaka
お気に入りにしたユーザー ProblemId : 5497 / 自分の提出
問題文最終更新日: 2022-07-19 23:52:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 352 (順位表) の他の問題:

Problem Statement

Kiri-kun loves drinking programming contests. A drinking programming contest is a contest in which you solve problems while drinking alcohol. It is known that drinking alcohol clears the mind and so raises one's ability to come up with ideas, but it also increases mistakes and so lowers one's implementation ability.
This contest has a total of $N$ problems, from problem $1$ to problem $N$. Kiri-kun solves these problems in order, starting from problem $1$. Each problem is divided into an idea part and an implementation part. When he has drunk a cumulative total of $x$ of alcohol, the time required for the $i\ (1\le i\le N)$-th problem is $\displaystyle\frac{A_i}{1+x}$ minutes for the idea part and $B_i(1+x)$ minutes for the implementation part. Kiri-kun can drink as much alcohol as he likes before starting each problem. Given that he starts the contest without having drunk any alcohol, find the minimum time required to finish solving all the problems. The time it takes to drink alcohol can be ignored.

Input

$N$
$A_1\ A_2\ \cdots\ A_N$
$B_1\ B_2\ \cdots\ B_N$

All inputs are integers.
$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)$

Output

Output the answer. Your answer will be considered correct if its absolute or relative error from the correct answer is at most $10^{-6}$. Print a newline at the end.

Sample

Sample 1
Input
2
2 18
3 2
Output
17

It is optimal to drink no alcohol before starting problem 1, and to drink $2$ (corrected at 21:35) of alcohol before starting problem 2. In this case, problem 1 takes $2$ for the idea part and $3$ for the implementation part, for a total time of $5$. Problem 2 takes $18\div 3=6$ for the idea part and $2\times 3 = 6$ for the implementation part, for a total time of $12$. In total, all the problems can be solved in a time of $17$. The time cannot be made shorter than $17$, so printing 17 is correct.

Sample 2
Input
2
18 2
2 3
Output
20

The order of the problems is reversed from Sample 1. It is optimal to drink $1$ (corrected at 21:35) of alcohol first. In this case, problem 1 takes $18\div 2 = 9$ for the idea part and $2\times 2 = 4$ for the implementation part, for a total time of $13$, and problem 2 takes $2\div 2=1$ for the idea part and $3\times 2 = 6$ for the implementation part, for a total time of $7$, so the total time required is 20. Note that problem 2 cannot be solved first.

Sample 3
Input
1
2
1
Output
2.8284271247

It is optimal to drink $\sqrt2-1$ (corrected at 21:35) of alcohol before starting problem $1$, in which case the whole takes a time of $2\sqrt2$. Your answer will be considered correct if its absolute or relative error from the correct answer is at most $10^{-6}$.

Sample 4
Input
1
1
2
Output
3

It is optimal not to drink any alcohol at all.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。