eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Насіння

Насіння

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

На базарі є ряд з N місць, де продається насіння соняшника. Потенційні покупці йдуть вздовж ряду, потім у деякий момент зупиняються і купують насіння. Якість насіння від місця до місця відрізняється непомітно, так що різниця лише у ціні насіння та положенні місця.

Перед тем як вийти на ринок в якості ще одного продавця насіння, Ви провели дослідження ринку, щоб знайти залежність числа покупців від двох названих факторів. Дослідження показали, що більшість покупців дотримуються одного й того ж шаблону. Вони проходять мимо декількох місця, помічаючи та запоминаючи ціни, а потім після обходу K місць, повертаються до місця з найменшою поміченою ціною, здійснюють там покупку, потім залишають базар. Якщо є декілька місць з однаковою ціною, покупець вибирає найближче.

Припустимо, что є п'ять місця з цінами 37, 34, 34, 35, 33. Якщо покупець з K = 4 йде зліва праворуч, він бачить насіння по цінам 37, 34, 34, 35. У цей момент він вирішує, що бачив достатньо, повертається до третього місця і купує насіння там. Хоча на другому місці ціна та ж, що і на третьому, покупцю до нього йти дальше. Якби би той же покупець зайшов праворуч, він би побачив ціни 33, 35, 34, 34, потім зупинився і повернувся б до п'ятого місця.

Число місць, пройдених до прийняття рішення (K), є функцією жадібності та терпеливості покупця, і, очевидно, відрізняється у різних покупців. Дослідження виявило средній процент B_K покупців для всіх значень K (1KN, 0B_K99, сума всіх B_K рівна 100).

Вам необхідно визначити оптимальну стратегію на цьому ринку (тобто ціну і положення нового місця, яке максимізує очікуваний середній прибуток) у припущенні, що половина клієнтів йде у напрямку від першого місця до N-го, а друга половина - від N-го місця до першого, і вони дотримуються описаного шаблону.

Вхідні дані

У першому рядку знаходиться число існуючих місць N, у другому рядку - N цілих чисел - ціни на кожному місці, у третьому рядку - N цілих чисел у діапазоні від 0 до 99 - значення B_K для кожного K (2N100, задані ціни - цілі числа від 1 до 9999). Всі числа у рядках відокремлено пропусками.

Вихідні дані

Виводиться два цілих числа - L і P. L (0 < L < N) - це число існуючих місць, після яких повинно бути розміщено нове (Вам не дозволяється встановлювати своє місце першим чи останнім). Число P - оптимальна ціна. Якщо існує більше ніж один оптимальний розв'язок, Ви повинні вибрати розв'язок з мінімальниым L, а серед них - з мінімальним P.

Приклад

Вхідні дані #1
5
37 34 34 35 33
10 20 30 30 10
Вихідні дані #1
2 33