| VK Cup 2016 - Раунд 1 |
|---|
| Закончено |
Лимак вырос и стал большим мишкой. Он приготовил n задач для соревнований по спортивному программированию. Изначальная стоимость (количество очков за успешное решение) i-й задачи равна pi. Прорешивание показало, что на решение i-й задачи требуется ровно ti минут. Задачи не обязательно упорядочены по сложности, но менять порядок уже поздно — Лимак уже объявил разбалловку в посте на главной странице. Единственное, что ещё можно поменять, это скорость убывания стоимости задач c.
Обозначим за T время, необходимое для решения всех задач, то есть T = t1 + t2 + ... + tn. Контест продлится ровно T минут, то есть как раз столько, сколько нужно чтобы всё решить.
Баллы за решение задачи линейно убывают со временем. Решение задачи i на минуте x даёт ровно 
, где константу 
предстоит выбрать Лимаку.
Предположим значение c фиксировано. Во время соревнования каждый участник выберет какой-нибудь порядок решения задач. Всего возможных порядков n!, каждый из них приведёт к какому-нибудь итоговому количеству очков, не обязательно целочисленному. Скажем, что порядок является оптимальным, если он даёт максимальное количество очков. Другими словами, решение задач в любом другом порядке даст количество очков меньшее либо равное, чем решение задач в таком порядке. Очевидно, что существует хотя бы один оптимальный порядок, однако, оптимальных порядков может быть и несколько.
Лимак предполагает, что каждый участник сразу правильно оценит значение ti для каждой задачи и начнёт решать их в каком-нибудь оптимальном порядке. Также Лимак полагает, что тестеры правильно определили все значения ti.
Для двух различных задач i и j, таких что pi < pj Лимак не хотел бы допустить ситуации, что какой-нибудь участник решавший задачи в оптимальном порядке получил за задачу i строго больше очков, чем за задачу j. Такую ситуацию Лимак называется парадоксом.
Несложно показать, что для c = 0 парадокс невозможен. Однако, для больших значений c это не так. Какое максимальное значение c (но помните, что ) можно выбрать, так чтобы парадокс был невозможен? Другими словами, чтобы для любого оптимального порядка решения задач не произошло парадокса.
Можно доказать, что максимальное c всегда существует.
В первой строке входных данных записано число n (2 ≤ n ≤ 150 000) — количество задач.
Во второй строке записаны n целых чисел p1, p2, ..., pn (1 ≤ pi ≤ 108) — изначальные стоимости задач.
В третье строке записаны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 108), i-е из которых означает количество минут, необходимое для решения i-й задачи.
Выведите единственное вещественное число — максимальное значение c, такое что и ни в одном оптимальном порядке решения задач не произойдёт парадокса. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
3
4 3 10
1 1 8
0.62500000000
4
7 20 15 10
7 20 15 10
0.31901840491
2
10 20
10 1
1.00000000000
В первом примере 3 задачи. Первая обладает параметрами (4, 1) (изначальная стоимость равна 4, а на решение требуется 1 минута), вторая (3, 1) и третья (10, 8). Продолжительность контеста равна T = 1 + 1 + 8 = 10.
Покажем наличие парадокса при c = 0.7. Решение задач в порядке 1, 2, 3 даст максимальное количество очков, равное:
- решение задачи через 1 минуту после начала:
- решение задачи через 2 минуты после начала:
- решение задачи через 10 минут после начала:
Таким образом, решение задач в таком порядке даёт 3.72 + 2.58 + 3 = 9.3 очков и это единственный оптимальный порядок (можно проверить ответы для других 5 перестановок). Однако, для задач 1 и 3 возникнет парадокс: 4 < 10, но 3.72 > 3. При c = 0.625 парадокса нет и это максимальное такое значение c.
Во втором примере, все 24 порядка решения задач являются оптимальными.
В третьем примере не возникнет парадокса даже при c = 1.
