chests[i] — число монет в i-м сундуке. Вы и соперник забираете их по очереди, начинаете вы.
Есть общий для обоих параметр M, сначала M = 1. За ход игрок забирает несколько первых оставшихся сундуков подряд — от 1 до 2·M штук, скажем X, — и после этого M становится равным max(M, X). Игра идёт, пока сундуки не кончатся.
Оба играют наилучшим образом: каждый стремится набрать как можно больше монет. Сколько монет достанется вам?chests=[3, 1, 4, 1, 5] → 8
Выгодно начать с одного сундука (3). Если соперник возьмёт два (1 и 4), вам достанутся оба оставшихся — 9. Поэтому он возьмёт один (1), а вы — два следующих (4 и 1), и ему останется 5. У вас 3 + 4 + 1 = 8. Если же сразу взять два сундука, соперник заберёт все три оставшихся, и у вас будет лишь 4.
chests=[5, 1, 1, 8] → 13
chests=[12] → 12
Единственный сундук достаётся вам.
chests=[3, 1, 4, 1, 5]
8
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 98 тестов на сервере, включая скрытые.