1578: More Nim

Nim is a game in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The player to remove the last object is the winner. You and your friend got tired of the same old game so you decided to try something different. The modified game consists of two phases. In the first phase you first take a turn removing as many entire heaps as you want. Your opponent then takes a turn removing as many heaps as he wants. Both you and your opponent are allowed to take no heaps, but are not allowed to take all the remaining heaps. After this the second phase starts in which the game continues as a normal Nim game.

The input file contains n sets of data, that you can get n from the first line of the file. Then in each set, you are given a String[] where each element represents the number of objects in a single heap at the beginning of the game. Each set ends with string of “0”. heaps will contain between 1 and 50 elements, inclusive. Each element of heaps will contain digits (‘0‘ - ‘9‘) only. Each element of heaps will represent a positive integer without leading zeros. Each element of heaps will contain between 1 and 16 characters, inclusive.

Output the minimum total number of objects you must remove in the first phase to ensure your victory even if your friend plays optimally, one string per line.

3
5 5 6 6 5 5 0
1 2 3 0
1 2 4 8 16 32 64 128 256 0

21
1
0

In Sample1, if you‘re left with two equal piles at the end of the first phase, you will lose the game. In each turn, however many objects you remove from a heap, your opponent will remove the same number of objects from the other heap, and you will eventually lose. To prevent this from happening, remove three of the heaps containing 5 objects and one of the heaps containing 6 objects (for a total of 21 objects). In Sample 2, the piles are distinct, but if you are presented with them at the beginning of the second phase, you will lose the game. No matter how many objects you remove during your turn, your opponent will be able to make a move that leaves you with two equal piles in your next turn. Removing the heap of size 1 during the first phase will guarantee your victory.