fares[i] — стоимость билета на остановку номер i + 1. Нужно получить доступ ко всем остановкам маршрута.
Действует акция: купив билет на остановку номер i, вы бесплатно получаете следующие i остановок (номера от i + 1 до 2i). Остановку, доставшуюся бесплатно, всё равно можно купить — ради её собственного бонуса.
Верните наименьшую сумму, за которую можно получить все остановки.fares=[4, 10, 1, 7] → 5
Покупаем билет на остановку 1 (4) — остановка 2 бесплатно. Билет на остановку 3 (1) открывает остановки 4 и 5, так что остановка 4 тоже бесплатна. Итого 5.
fares=[3, 1, 9, 9, 9] → 12
Покупаем остановку 1 за 3 — остановка 2 бесплатна. Затем остановку 3 за 9: она открывает остановки 4, 5 и 6. Итого 12. Купить дешёвую остановку 2 соблазнительно, но остановку 5 она не покрывает, и всё равно придётся платить 9.
fares=[6] → 6
fares=[4, 10, 1, 7]
5
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 120 тестов на сервере, включая скрытые.