Последние несколько дней у детектива Алексея нет дел, и он почти полностью проводит…
- User
Последние несколько дней у детектива Алексея нет дел, и он почти полностью проводит время в увлекательнейшей игре, на которую его подсадил его сын Георгий — «Побоище», игровой процесс которой настолько разнообразен и занимателен, что о нём не получится рассказать в этом условии. У Алексея есть некоторое количество внутриигровой валюты, которую он получает за выполнение квестов. В частности, игра содержит следующий квест: При заходе в игру на i𝑖-й день подряд игрок поощряется ai𝑎𝑖 единицами валюты; такой квест можно выполнять не более n𝑛 дней подряд, после чего счётчик дней сбрасывается до единицы. Таким образом, если заходить в игру n+1𝑛+1 день подряд, то в последний из этих дней игрок получит a1𝑎1 денег. Конечно, можно пропустить один день и не заходить в игру вообще; тогда счётчик дней также сбросится до единицы. Ясно, что Алексей хочет получать с этого квеста как можно больше денег. Возможно, награды распределены так, что выгодно в какой-то из дней не заходить в игру, чтобы начать цикл заново. Так как Алексей не планирует прекращать играть в «Побоище» даже при появлении дел, его интересует такая стратегия, при которой средняя прибыль в день максимальна. Помогите ему решить эту задачу. Входные данные В первой строке ввода дано единственное натуральное число n𝑛 (1⩽n⩽1051⩽𝑛⩽105). Во второй строке ввода перечислены n𝑛 целых чисел a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛, где ai𝑎𝑖 — награда за посещение i𝑖 дней подряд (1⩽ai⩽1091⩽𝑎𝑖⩽109). Выходные данные Выведите единственное число x𝑥 — номер дня с начала цикла, после которого нужно день не заходить в игру; средняя прибыль в день при таком выборе должна быть максимальна. Если выгодней всего заходить в игру каждый день, выведите число n𝑛. Я не очень понимаю условие. Вот примеры тестов. Объясни их 3 7 10 1 Второй пример 10 15 6 17 11 1 1 1 1 1 7
- Assistant
Давай разберем оба примера, чтобы понять, как вычисляется оптимальная стратегия для максимизации средней прибыли.
Первый пример:
Число дней ( n = 3 ). Награды за каждый день таковы: ( a_1 = 7 ), ( a_2 = 10 ), ( a_3 = 1 ).
- Если заходить в игру каждый день, то энергия на первый день цикла будет ( 7 + 10 + 1 = 18 ), потом снова ( 7 + 10 + 1 = 18 ), и так далее, это дает в среднем ( 18 / 3 = 6 ) единиц валюты в день.
- Если день пропустить после первого дня (( a_1 = 7 )), то следующий цикл начнется сразу с первого дня, и получится усреднение ( 7 ).
- Если день пропустить после второго дня (( a_2 = 10 )), следовательно, у нас получится усреднение ( (7 + 10) / 2 = 8.5 ).
- Если день пропустить после третьего дня (( a_3 = 1 )), снова получится усреднение ( 6 ).
Таким образом, максимальная средняя прибыль будет, когда мы пропустим день после второго дня (( a_2 )), и это дает нам максимум ( 8.5 ) единиц валюты в день.
Второй пример:
Число дней ( n = 10 ). Награды таковы: ( a_1 = 15 ), ( a_2 = 6 ), ( a_3 = 17 ), ( a_4 = 11 ), ( a_5 = 1 ), ( a_6 = 1 ), ( a_7 = 1 ), ( a_8 = 1 ), ( a_9 = 1 ), ( a_{10} = 7 ).
Посмотрим, как лучше всего пропускать дни:
- Заходим каждый день и ни разу не пропускаем, общая сумма получится ( 15 + 6 + 17 + 11 + 1 + 1 + 1 + 1 + 1 + 7 = 60 ) валюты, в среднем это ( 60 / 10 = 6 ) единиц в день.
- Проверим стратегии с пропуском:
- Пропустим день после первого: итоговая усредненная прибыль ( (15 + 6) / 2 = 10.5 ).
- Пропустим день после второго: ( (15 + 6 + 17) / 3 = 12.67 ).
- Пропустим день после третьего: ( (15 + 6 + 17 + 11) / 4 = 12.25 ).
И так дальше до десятого дня. Каждый раз вычисляем среднюю прибыль и сравниваем.
В итоге, для второго примера максимальная прибыль получается, если всегда заходить в игру, смысл не имеет пропустить день, поскольку усредненная прибыль не станет выше. Таким образом, оптимальной стратегией является вход в игру все 10 дней подряд.
Поэтому в первом примере правильный ответ будет ( x = 2 ) и во втором случае ( x = 10 ).