Statistics

Problem Statement for "MoneyGame"

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

  1. {0,1,1}

    {0,1,1}

    {20,10,2}

    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.

  2. {0,1,2}

    {0,1,1}

    {20,10,2}

    Returns: 2

    The same game as Example 0, but in this case the extra coin makes a difference, as Lenny wins 2.

  3. {1,1,0}

    {0,0,1}

    {1,5,10}

    Returns: 0

    This game turns out to be a draw.

  4. {4,4,3}

    {4,3,4}

    {100,753,100}

    Returns: 600

  5. {5,5,5}

    {5,5,5}

    {1,1,1}

    Returns: 0

  6. {5,5,5}

    {5,5,5}

    {1,5,10}

    Returns: -3

  7. {5,5,5}

    {5,5,5}

    {1,10,100}

    Returns: -19

  8. {0,0,0}

    {5,5,5}

    {1000,1000,1000}

    Returns: -15000

    Lenny loses a lot of money.

  9. {3,2,1}

    {0,0,0}

    {6,8,14}

    Returns: 42

  10. {5,5,5}

    {5,5,4}

    {25,5,1}

    Returns: 0

  11. {4,3,2}

    {0,3,5}

    {9,24,351}

    Returns: -729

  12. {0,0,1}

    {0,1,1}

    {10,5,1}

    Returns: -5

  13. {0,1,1}

    {0,0,1}

    {100,10,1}

    Returns: 2

  14. {5,5,1}

    {3,3,3}

    {11,420,213}

    Returns: 431

  15. {4,2,5}

    {4,4,1}

    {544,90,184}

    Returns: 818

  16. {1,4,4}

    {2,5,5}

    {368,55,32}

    Returns: -586

  17. {1,2,0}

    {4,1,2}

    {103,852,68}

    Returns: -548

  18. {2,5,1}

    {0,4,4}

    {86,144,968}

    Returns: -2598

  19. {5,5,3}

    {2,2,1}

    {921,445,804}

    Returns: 6331

  20. {2,4,4}

    {5,1,1}

    {480,984,752}

    Returns: 4864

  21. {5,5,3}

    {0,5,5}

    {307,607,991}

    Returns: -1228

  22. {2,4,5}

    {5,4,1}

    {182,135,344}

    Returns: 1127

  23. {4,1,0}

    {0,3,5}

    {202,337,62}

    Returns: -714

  24. {0,5,1}

    {4,3,5}

    {515,140,89}

    Returns: -2315

  25. {1,2,3}

    {2,5,5}

    {816,587,654}

    Returns: -5484

  26. {2,5,3}

    {0,1,2}

    {194,111,749}

    Returns: 2247

  27. {2,0,1}

    {4,2,5}

    {998,794,311}

    Returns: -5654

  28. {5,5,4}

    {1,3,4}

    {611,1,53}

    Returns: 2501

  29. {5,0,4}

    {5,4,1}

    {476,726,266}

    Returns: -3444

  30. {4,5,0}

    {1,5,1}

    {620,88,124}

    Returns: 1624

  31. {5,1,0}

    {5,5,5}

    {158,900,268}

    Returns: -5462

  32. {3,4,4}

    {5,4,4}

    {537,989,879}

    Returns: -1611

  33. {2,1,3}

    {3,1,0}

    {389,192,484}

    Returns: 1551

  34. {2,0,0}

    {1,3,5}

    {642,177,576}

    Returns: -3522

  35. {2,3,5}

    {0,1,1}

    {512,462,627}

    Returns: 4521

  36. {5,0,5}

    {5,5,1}

    {500,501,608}

    Returns: 0

  37. {0,5,1}

    {5,2,3}

    {223,953,25}

    Returns: -992

  38. {4,5,5}

    {4,5,5}

    {747,977,93}

    Returns: -465

  39. {5,5,5}

    {5,5,5}

    {1000,980,957}

    Returns: -957

  40. {4,4,4}

    {4,4,4}

    {800,297,400}

    Returns: -297

  41. {0,0,0}

    {0,0,0}

    {10,3,5}

    Returns: 0

  42. {1,3,5}

    {4,2,2}

    {575, 575, 229}

    Returns: -458

  43. {4,2,0}

    {5,0,0}

    {1,77,77}

    Returns: 84

  44. {3,5,1}

    {1,1,5}

    {404, 303, 404}

    Returns: 0

  45. {0,1,1}

    {0,1,1}

    {10,5,1}

    Returns: -1

  46. {0,0,0}

    {0,0,0}

    {1000,352,283}

    Returns: 0

  47. {5, 5, 5 }

    {5, 5, 5 }

    {3, 2, 1 }

    Returns: -1

  48. {5, 5, 5 }

    {5, 5, 5 }

    {1, 100, 10 }

    Returns: -19

  49. {5, 5, 5 }

    {5, 5, 5 }

    {1, 100, 11 }

    Returns: -20

  50. {5, 5, 5 }

    {5, 5, 5 }

    {1, 1, 1000 }

    Returns: -2

  51. {4, 5, 4 }

    {5, 4, 4 }

    {454, 140, 846 }

    Returns: -560

  52. {5, 4, 5 }

    {5, 5, 4 }

    {454, 140, 846 }

    Returns: 560

  53. {5, 5, 5 }

    {5, 5, 5 }

    {1000, 100, 10 }

    Returns: -190

  54. {5, 5, 5 }

    {5, 5, 5 }

    {1, 2, 3 }

    Returns: -1

  55. {5, 5, 5 }

    {5, 5, 5 }

    {121, 1, 11 }

    Returns: -20

  56. {5, 5, 5 }

    {5, 5, 5 }

    {1, 100, 1000 }

    Returns: -109

  57. {4, 5, 5 }

    {5, 4, 5 }

    {100, 753, 100 }

    Returns: 600

  58. {4, 4, 3 }

    {4, 3, 4 }

    {100, 753, 100 }

    Returns: 600

  59. {5, 5, 5 }

    {5, 4, 5 }

    {1, 15, 1000 }

    Returns: 20

  60. {5, 5, 5 }

    {5, 5, 5 }

    {100, 100, 100 }

    Returns: 0

  61. {5, 5, 5 }

    {5, 5, 5 }

    {1, 980, 37 }

    Returns: -46

  62. {4, 5, 3 }

    {2, 5, 5 }

    {16, 545, 128 }

    Returns: -416

  63. {5, 5, 5 }

    {5, 5, 5 }

    {1, 30, 1000 }

    Returns: -39

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: