← 返回题目列表

AtCoder · agc040_d

D. 平衡木

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

分数: 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