printПеребор

printСемечки

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

На базаре есть ряд из `N` мест, где продаются семечки подсолнечника. Потенциальные покупатели идут вдоль ряда, затем в некоторый момент останавливаются и покупают семечки. Качество семечек от места к месту различается незначительно, так что разницы только в цене семечек и положении места.
Перед тем как выйти на рынок в качестве ещё одного продавца семечек, Вы провели исследование рынка, чтобы найти зависимость числа покупателей от двух названных факторов. Исследование показывает, что большинство покупателей следуют одному и тому же шаблону. Они проходят мимо нескольких мест, замечая и запоминая цены, а затем после обхода `K` мест, возвращаются к месту с наименьшей замеченной ценой, совершают там покупку, затем покидают базар. Если есть несколько мест с одинаковой ценой, покупатель выбирает ближайшее.
Предположим, что есть пять мест с ценами 37, 34, 34, 35, 33. Если покупатель с `K\ =\ 4` идёт слева направо, он видит семечки по ценам 37, 34, 34, 35. В этот момент он решает, что видел достаточно, возвращается к третьему месту и покупает семечки там. Хотя на втором месте цена та же, что и на третьем, покупателю до него идти дальше. Если бы тот же покупатель зашёл справа, он бы увидел цены 33, 35, 34, 34, затем остановился и вернулся бы к пятому месту.
Число мест, пройденных до принятия решения (`K`), является функцией жадности и терпеливости покупателя, и, очевидно, различается у разных покупателей. Исследование выявило средний процент `B_K` покупателей для всех значений `K\ (1\ ≤\ K\ ≤\ N,\ 0\ ≤\ B_K\ ≤\ 99`, сумма всех `B_K` равна 100).
Вам следует определить оптимальную стратегию на этом рынке (то есть цену и положение нового места, которое максимизирует ожидаемый средний доход) в предположении, что половина клиентов идёт в направлении от первого места к `N`-му, а другая половина – от `N`-го места к первому, и они следуют описанному шаблону.
Ввод
В первой строке находится число существующих мест `N\ (2\ ≤\ N\ ≤\ 100)`, во второй строке — `N` целых чисел от 1 до 9999— цены на каждом месте, в третьей строке — `N` целых чисел в диапазоне от 0 до 99 — значения `B_K` для каждого `K`. Все числа в строках разделены пробелами.
Вывод
Выводятся два целых числа — `L` и `P`. `L\ (0\ <\ L\ <\ N)` – это число существующих мест, после которых должно быть размещено новое (Вам не разрешается устанавливать своё место первым или последним). Число `P` – оптимальная цена. Если существует более чем одно оптимальное решение, Вы должны выбрать решение с минимальным `L`, а среди них – с минимальным `P`.

Пример ввода

5
37 34 34 35 33
10 20 30 30 10

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

2 33
Источник: Far-Eastern quarterfinal, NEERC, 2001
loading