Julianne invited her two friends Michael and Jane to a cake party.
When Michael and Jane arrived, they
saw that their host had prepared several tables. On each table there was a plate with one
of the cakes. Each cake was cut into several pieces.
Not knowing where to start, Michael and Jane decided to play the following game:
Players take alternating turns. In each turn the player selects one cake, and takes and eats several pieces of the cake.
The player must take and eat at least one piece. The player who eats the last piece of the last cake wins.
However, the host would be really offended if she had the impression that the guests didn't like some of her cakes. Therefore Michael and Jane agreed on one additional rule: Each time a player selects a cake, he or she may only select one of those cakes that have the most pieces remaining.
Michael starts the game and plays optimally. In other words, if there is a strategy that will ensure his win (no matter how Jane plays),
he will follow one such strategy. If he finds himself in a position where no strategy can guarantee him winning the game he just makes a valid move.
In addition, whenever Michael has more than one move to choose from, he picks the lexicographically
smallest one (explained below).
You are given a int[] pieces. The i-th element of pieces is the initial number of pieces of the i-th cake.
Return Michael's first move as a String formatted as follows: "CAKE C PIECES P", where
C is the zero-based index of the cake he should select and P is the number of pieces he should eat.
The numbers C and P must not contain unnecessary leading zeroes.
In case there are multiple valid answers return the one where the resulting String is lexicographically smallest.
|