Problem Statement |
| |
Frugal Fred and Lucky Lenny were talking the other day, and Fred challenged Lenny to a game. The rules for the game were as follows:
- Lenny goes first.
- On a player's turn, he must place one coin into an initially empty pot.
- After placing a coin into the pot, the player may then remove any number of coins from the pot, such that the total value of all coins removed is less than the value of the coin placed in the pot.
- The game ends when a player cannot put a coin into the pot on their turn; that player loses. The loser must pay the winner an amount equal to the value of the coins that the winner is holding.
Lenny is afraid that Fred has stacked the game in his favor, so he has asked you to find out the outcome if both players play optimally. There are 3 types of coins. You are given a int[] values, where the i-th element is the value of the i-th type of coin. You are also given int[]s lennysCoins and fredsCoins, where the i-th element of each is the number of coins of the i-th type initially held by Lenny and Fred, respectively.
Return the amount of money Lenny receives in this game, assuming that both play optimally. If Lenny must lose money, return this as a negative number (e.g., if Lenny must lose 2, then this will be returned as -2).
|
| |
Definition |
| | | Class: | MoneyGame | | Method: | play | | Parameters: | int[], int[], int[] | | Returns: | int | | Method signature: | int play(int[] lennysCoins, int[] fredsCoins, int[] values) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | lennysCoins and fredsCoins will each contain exactly 3 elements. |
| - | Each element of lennysCoins and fredsCoins will be between 0 and 5, inclusive. |
| - | values will contain exactly 3 elements. |
| - | Each element of values will be between 1 and 1000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: -2 | | Optimally played, Lenny starts by playing his 2 cost coin. Fred plays his 10 cost coin, taking a 2 cost coin out of the pot. Lenny plays his 10 cost coin, and Fred (holding two 2 cost coins) plays one of them. Lenny has no coins left, and so must pay Fred 2. |
|
|
| 1) | |
| | | Returns: 2 | | The same game as Example 0, but in this case the extra coin makes a difference, as Lenny wins 2. |
|
|
| 2) | |
| | | Returns: 0 | | This game turns out to be a draw. |
|
|
| 3) | |
| | {4,4,3} | {4,3,4} | {100,753,100} |
| Returns: 600 | |
|
| 4) | |
| | {0,0,0} | {5,5,5} | {1000,1000,1000} |
| Returns: -15000 | | Lenny loses a lot of money. |
|
|
| 5) | |
| | |