chests[i] is the number of coins in chest i. You and an opponent take them in turns, and you go first.
Both players share a parameter M, which starts at M = 1. On a turn, a player takes some of the first remaining chests in a row, anywhere from 1 to 2·M of them, say X, and then M becomes max(M, X). The game goes on until no chests are left.
Both play optimally, each trying to collect as many coins as possible. How many coins do you end up with?chests=[3, 1, 4, 1, 5] → 8
It pays to start with one chest (3). If the opponent then takes two (1 and 4), both remaining chests go to you for 9 in total. So the opponent takes one (1), you take the next two (4 and 1), and the opponent gets the 5. You end with 3 + 4 + 1 = 8. Taking two chests at the start would let the opponent take all three remaining ones, leaving you with only 4.
chests=[5, 1, 1, 8] → 13
chests=[12] → 12
The only chest is yours.
chests=[3, 1, 4, 1, 5]
8
Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.