Семечки

На базаре есть ряд из 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-го места к первому, и они следуют описанному шаблону.

Входные данные

В первой строке входного файла INPUT.TXT находится число существующих мест N (2 ≤ N ≤ 100), во второй строке N целых чисел – цены на каждом месте, в третьей строке – N целых чисел в диапазоне от 0 до 99 – значения B_K для каждого K. Все числа в строках разделены пробелами.

Выходные данные

В выходной файл OUTPUT.TXT выведите два целых числа: L и P. L (0 < L < N) – это число существующих мест, после которых должно быть размещено новое (Вам не разрешается устанавливать своё место первым или последним). Число P – оптимальная цена. Если существует более чем одно оптимальное решение, Вы должны выбрать решение с минимальным L, а среди них – с минимальным P.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]