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