printРабочее место участника

printЗадачи

216. Как мужик двух генералов накормил

Ограничения: время – 5s/10s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Мужику нужно накормить двух генералов. Чем дольше они едят, тем они более счастливы. Для этого Мужик приготовил N горшков каши. Генерал-1 съедает `k`-ый горшок каши за `a_k` минут, а Генерал-2 – за `b_k` минут.
Поедание каши происходит следующим образом. Горшки выстраиваются в ряд. Генерал-1 начинает есть с одного конца, а Генерал-2 – с другого. Возможно, что в конце они одновременно будут есть из одного горшка. Каждый Генерал ест кашу из одного горшка с постоянной скоростью.
Требуется определить, за какое наибольшее время генералы съедят кашу.
В первой ввода записано число `N\ (N≤256)`, далее следует `N` строк, а в каждой через пробел пара вещественных чисел `a_k` и `b_k` – время поедания каши.
Вывести одно число – максимальное время еды с 3 десятичными знаками.

Пример ввода

4
1 2
1 2
0.5 1.5
7 3.5

Пример вывода

6.000
Источник: http://neerc.ifmo.ru/school/archive/
loading