TopCoder problem "StoneGame" used in SRM 345 (Division I Level Two)

Problem Statement


You and your friend are playing a game. There is a number of treasure chests hidden under piles of stones. That is, the i-th chest has stones[i] stones piled on top of it. You take turns taking exactly one stone from the top of one of the chests. Whoever takes the last stone from the top of a chest takes the chest and the treasure inside. The inside of the i-th chest is worth treasure[i]. The game objective is to gather as much treasure as possible.

Unfortunately, your friend is a cyborg and always makes the best possible move (maximizing his final win). Given stones and treasure, return the maximum total amount you can get from the chests given that you move first.



Parameters:int[], int[]
Method signature:int getScore(int[] treasure, int[] stones)
(be sure your method is public)


-stones will contain between 1 and 50 elements, inclusive.
-stones and treasure will contain the same number of elements.
-Each element of stones will be between 1 and 10^6, inclusive.
-Each element of treasure will be between 1 and 10^6, inclusive.


Returns: 5
In your first move you take the stone from the 0-th chest and take its treasure. Then your friend must take a stone from the 1-st chest leaving you with one stone on the 1-st chest. You take the last stone in your second move and take the contents of the 1-st chest.
Returns: 9
Returns: 0
Returns: 0

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Math, Sorting