分数: 1100 点
问题陈述
我们有 N 平衡木编号 1 to N。 每根梁的长度为 1 米。 Snuke 在光束上行走 i 速度为 1/A_i 米每秒,林戈在光束上行走 i 速度为 1/B_i 米每秒。
Snuke 和 Ringo 将玩以下游戏:
- 首先,Snuke 连接 N 以他选择的任何顺序进行横梁,并形成长度较长的横梁 N 米。
- 然后,Snuke 从长梁的左端开始。与此同时,林戈从长梁上均匀随机选择的点开始。两人走到长梁的右端。
- Snuke 获胜当且仅当他在 Ringo 到达长梁右端之前追上 Ringo。也就是说,如果有某个时刻Snuke和Ringo站在同一位置,则Snuke获胜,否则Ringo获胜。
求当 Snuke 排列时 Snuke 获胜的概率 N 光束使他获胜的概率最大化。
这个概率是一个有理数,所以我们要求你将它表示为一个不可约分数 P/Q (代表 0,使用 P=0, Q=1).
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
打印代表 Snuke 获胜最大概率的不可约分数的分子和分母。
示例输入 1
2 3 2 1 2
示例输出 1
1 4
当梁按顺序连接时 2,1 从左到右,Snuke获胜的概率为 1/4,这是最大可能值。
示例输入 2
4 1 5 4 7 2 1 8 4
示例输出 2
1 2
示例输入 3
3 4 1 5 2 6 3
示例输出 3
0 1
示例输入 4
10 866111664 178537096 705445072 318106937 472381277 579910117 353498483 865935868 383133839 231371336 378371075 681212831 304570952 16537461 955719384 267238505 844917655 218662351 550309930 62731178
示例输出 4
697461712 2899550585