PROBLEM DESCRIPTION
Your bratty little brother left three big piles of toys sitting out in YOUR
room and your mother has informed you archly that they Must Be Picked Up
Posthaste. When you protested and he laughed at you, your mom muttered
something under her breath that sounded like "puerile callow mendacious
vexations" (you didn't quite understand what all those words meant), then sent
both of you off to pick them up.
Now the little snotnose wants to play a game with you and is willing to wager
the week's allowance money. The two of you will take turns picking up toys
from one pile of your choice. (The pile you choose to pick up toys from can be
different each turn, but you cannot pick up toys from two or three different
piles on the same turn. You also cannot pass on your turn.) Because you can
only carry so much in your arms at one time, there is a strict limit to the
number of toys you can pick up in a given turn. Letting this number be k,
players are allowed to pick up anywhere from 1 to k toys on their turn,
inclusive. The one who can pick up the last toy from the floor wins. Your
brother has casually stated that since he is younger than you are, he should
get to go first.
You regard this last statement with grave suspicion. For all his
obnoxiousness, your little brother has shown a distinctive flair for
mathematics, and you suspect that the "innocent little tyke" may have actually
analyzed this game out to its conclusion in advance. With the week's allowance
money at stake, you decide that the risk of allowing the game to take its
natural course is unacceptable. You have instead chosen to cheat.
You have surreptitiously hidden some toys in your pocket, and you believe you
can sneak them into the corner of the first pile prior to the start of the
game. The question is, how many toys should you add to make the game turn out
in your favor?
In the following description, let A represent the player going first (your
brother) and B represent the player going second (you).
The method you write will take in the number of toys in each of the piles, and
the maximum number of toys that can be picked up at once. It should return the
minimum number of toys needed to add to the first pile to make player A lose,
assuming correct play by both sides. If no amount of additional toys can make
player A lose, return -1. (This corresponds to putting a headlock on the
little brat.)
DEFINITION
Class Name: CleanupCrew
Method Name: toysToAdd
Parameters: int, int, int, int
Returns: int
Method signature (be sure your method is public): int toysToAdd(int p1, int
p2, int p3, int k)
In the signature:
- p1, p2, p3 are the number of toys in each of the three piles. Thus, the
first pile starts out with p1 toys.
- k is the most number of toys that can be picked up at once
The toysToAdd() method should return the minimum number of toys to add to the
first pile prior to the start of the game, such that with correct play by both
sides, the player going first (player A) will always lose. The number of toys
added must be nonnegative. If player A will lose if the game is played out
without toys being added to the first pile, return 0. If player A can always
force a win regardless of the number of toys added to the first pile, return -1.
NOTES
Topcoder will enforce the following input constraints:
p1 is between 1 and 1000, inclusive.
p2 is between 1 and 1000, inclusive.
p3 is between 1 and 1000, inclusive.
k is between 1 and 20, inclusive.
EXAMPLES
toysToAdd(1,1,1,1) = 1. One toy is picked up on each turn, and there are an
odd number of toys to begin with. Therefore to make player B win, we must add
one toy to the first pile.
toysToAdd(1,1,2,1) = 0. Again, one toy is picked up on each turn. But here
there are an even number of toys, so player B already wins with no toys added.
toysToAdd(1,1,1,2) = 2. With one or two toys in the first pile, player A can
win by picking up all of the toys in the first pile on his first turn.
However, with three toys in the first pile, player B can force a win in all
cases. Thus we must add two toys.
toysToAdd(1,2,1,2) = -1. Player A can force a win regardless of how many toys
are added to the first pile.