/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 種類の品物がそれぞれ無限個あります。 i 種類目の品物は重さが A_i 、体積が B_i 、価値が C_i です。
レベル X の高橋君は、重さの合計が X 以下かつ体積の合計が X 以下になるように品物を持つことができます。ここで、高橋君は条件を満たすならば同じ種類の品物を何個でも持つことが可能であり、また選ばない種類の品物があっても構いません。
レベル X の高橋君が持てる品物の価値の合計の最大値を f(X) とするとき、極限 \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} が存在することが証明できます。この値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 10^8\leq A_i,B_i,C_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
出力
答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
2 100000000 200000000 100000000 200000000 100000000 100000000
出力例 1
0.6666666666666667
X=300000000 のとき、高橋君は重さの合計が 300000000 以下かつ体積の合計が 300000000 以下になるように品物を持つことができます。
持ち方の一例として、高橋君は 1 番目の品物と 2 番目の品物を 1 個ずつ持つことができます。このとき、品物の価値の合計は 100000000+100000000=200000000 であり、これが達成可能な価値の最大値なので、\dfrac{f(300000000)}{300000000}=\dfrac{2}{3} です。
また、この入力では極限 \displaystyle\lim_{X\to \infty} \dfrac{f(X)}{X} も \dfrac{2}{3} に一致することが証明できます。よって答えは 0.6666666... です。
入力例 2
1 500000000 300000000 123456789
出力例 2
0.2469135780000000
Score : 600 points
Problem Statement
There are N kinds of items, each with infinitely many copies. The i-th kind of item has a weight of A_i, a volume of B_i, and a value of C_i.
Level X Takahashi can carry items whose total weight is at most X and whose total volume is at most X. Under this condition, it is allowed to carry any number of items of the same kind, or omit some kinds of items.
Let f(X) be the maximum total value of items Level X Takahashi can carry. It can be proved that the limit \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} exists. Find this limit.
Constraints
- 1\leq N\leq 2\times 10^5
- 10^8\leq A_i,B_i,C_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
Output
Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{-6}.
Sample Input 1
2 100000000 200000000 100000000 200000000 100000000 100000000
Sample Output 1
0.6666666666666667
When X=300000000, Takahashi can carry items whose total weight is at most 300000000 and whose total volume is at most 300000000.
He can carry, for instance, one copy of the 1-st item and one copy of the 2-nd item. Then, the total value of the items is 100000000+100000000=200000000. This is the maximum achievable value, so \dfrac{f(300000000)}{300000000}=\dfrac{2}{3}.
It can also be proved that \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} equals \dfrac{2}{3}. Thus, the answer is 0.6666666....
Sample Input 2
1 500000000 300000000 123456789
Sample Output 2
0.2469135780000000