Scored Nim
Time limit2sMemory limit512 MB
Players alternately split a heap into two colored heaps until all heaps are size one; find Alice's optimal final white-stone count.
- Level
Hard8 of 10
- Topics
- Game theory, Dynamic programming, Math, Greedy
- Solved
- No attempts yet
Problem
Alice and Bob want to play Nim. Some kind of it, anyway.
Initially, they have n heaps of stones, the i-th heap containing ai stones. Players take alternating turns, and Alice moves first. On your turn, you choose any heap with at least two stones and split it into two new heaps with at least one stone in each. Then you color all stones in one of the new heaps white and all stones in the other one black. The game lasts until every heap contains only one stone.
After the game, Alice's score is the number of white stones on the board, and Bob's score is the number of black stones. Both players want to maximize their score and play optimally. What will be Alice's score?
Input
The first line of input contains a single integer n (1 ≤ n ≤ 128).
The second line of input contains n integers a1, a2, . . . , an (2 ≤ ai ≤ 128).
The initial colors of the stones are irrelevant.
Output
Output a single integer: Alice's score if both players play optimally.
Hint
In the example, no matter how players move, both heaps will be split between them equally.