← 返回题目列表

AtCoder · abc275_g

G. 无限背包

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 种物品,每种物品都有无限多份。的 i第一种物品的重量为 A_i,体积 B_i,值为 C_i.

等级 X 高桥最多可以携带总重量为 X 其总体积最多为 X。在此条件下,允许携带任意数量的同类物品,或省略某些种类的物品。

让 f(X) 为物品等级的最大总价值 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-st 项目和一份副本 2-第一项。那么物品的总价值就是 100000000+100000000=200000000。这是可实现的最大值,因此 \dfrac{f(300000000)}{300000000}=\dfrac{2}{3}.

还可以证明 \displaystyle\lim_{X\to \infty} \frac{f(X)}{X} 等于 \dfrac{2}{3}。因此,答案是 0.6666666....


示例输入 2

1
500000000 300000000 123456789

示例输出 2

0.2469135780000000