русский
english
E. Прикладная флористика
| Имя входного файла: | flowers.in |
| Имя выходного файла: | flowers.out |
| Ограничение по времени: | 3 s |
| Ограничение по памяти: | 256 megabytes |
Серёжа подарил Ане на день рождения n цветов различных видов. В энциклопедии Аня прочитала, что i–ый цветок вырастает со скоростью vi сантиметров в день и его изначальный рост равен hi сантиметров. Ане сразу же посадила все n цветов на грядку и теперь бегает каждый день и проверяет – не <<обогнал>> ли какой-нибудь цветок другого в росте. Серёже не нравится, что Аня всё своё свободное время проводит с цветами. Теперь его интересует, когда наступит день, после которого ни один другой цветок не сможет обогнать никакой другой цветок. Серёжа просит вас помочь ему определить этот день.
Рассмотрим процесс роста цветов на примере:
Пусть Ане подарили три цветка. Рост первого цветка 5 сантиметров, второго – 7 сантиметров, третьего – 1 сантиметр.
Скорость роста первого цветка 2 сантиметра в день, второго – 1 сантиметр в день, третьего – 3 сантиметра в день.
Изначально (в нулевой день) у цветов следующие высоты: 5 7 1.
В первый день: 7 8 4.
Во второй день: 9 9 7.
В третий день: 11 10 10 (первый цветок обогнал второй).
В четвертый день: 13 11 13 (третий цветок обогнал второй).
В пятый день: 15 12 16 (третий цветок обогнал первый).
Начиная с пятого дня никакие два цветка уже не обгонят друг друга, поэтому ответом является число 5.
Формат входного файла
В первой строке входного файла дано целое число n – количество различных видов цветов (1 ≤ n ≤ 105). В следующих n строках даны по два целых числа hi и vi – изначальный рост i–ого цветка и его скорость роста соответственно (0 ≤ hi, vi ≤ 109).
Формат выходного файла
В выходной файл выведите единственное число – номер искомого дня.
Пример:
| flowers.in | flowers.out |
|---|---|
| 3 5 2 7 1 1 3 | 5 |
| 1 0 0 | 0 |
| 2 5 1 6 1 | 0 |
Источник: Первенство ПетрГУ. Сентябрь 2012.
Обсудить Отправить решение
Версия для печати