405823: GYM102129 E Scored Nim

Alice and Bob want to play Nim. Well, some kind of it.

Initially, they have $$$n$$$ heaps of stones, $$$i$$$-th heap containing $$$a_i$$$ stones. Players take alternating turns, Alice moves first. On their turn, a player chooses any heap with at least two stones and splits it into two new heaps with at least one stone in each. After that, the player colors 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?

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 128$$$).

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \leq a_i \leq 128$$$).

Note that the initial colors of the stones are irrelevant.

Output a single integer: Alice's score if both players play optimally.

2
2 2

2

In the example, no matter how players move, both heaps will be split between them equally.