Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Бинарный поиск

Сканирование, метод двух указателей

Олимпиадные задачи на английском языке

Сканирование, метод двух указателей

Олимпиадные задачи на английском языке

06/12/2012 | Занятие 13 (Задачи NEERC 2012) (C) |

*Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Long long ago in a far far away land there were two great cities and The Great Caravan Road between
them. Many robber gangs "worked" on that road.

By an old custom the i-th band robbed all merchants that dared to travel between ai and bi miles of
The Great Caravan Road. The custom was old, but a clever one, as there were no two distinct `i` and
`j` such that `a_i\ ≤\ a_j` and `b_j\ ≤\ b_i`. Still when intervals controlled by two gangs intersected, bloody fights
erupted occasionally. Gang leaders decided to end those wars. They decided to assign each gang a new
interval such that all new intervals do not intersect (to avoid bloodshed), for each gang their new interval
is subinterval of the old one (to respect the old custom), and all new intervals are of equal length (to
keep things fair).

You are hired to compute the maximal possible length of an interval that each gang would control after
redistribution.

The first line contains `n` (`1\ ≤\ n\ ≤\ 100\ 000`) — the number of gangs. Each of the next n lines contains
information about one of the gangs — two integer numbers `a_i` and `b_i` (`0\ ≤\ a_i\ <\ b_i\ ≤\ 1\ 000\ 000`). Data
provided in the input file conforms to the conditions laid out in the problem statement

Output the maximal possible length of an interval in miles as an irreducible fraction `p/q`.

Sample Input

3 2 6 1 4 8 12

Sample Output

5/2

In the above example, one possible set of new intervals that each gang would control after redistribution
is given below.

- The first gang would control an interval between 7/2 = 3.5 and 12/2 = 6 miles which has length of 5/2 and is a subinterval of its original (2, 6).

- The second gang would control an interval between 2/2 = 1 and 7/2 = 3.5 miles which has length of 5/2 and is a subinterval of its original (1, 4).

- The third gang would control an interval between 16/2 = 8 and 21/2 = 10.5 miles which has length of 5/2 and is a subinterval of its original (8, 12).