PROBLEM DESCRIPTION
Your bratty little brother left two 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 both 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.
DEFINITION
Class Name: ToyPatrol
Method Name: toysToAdd
Parameters: int, int, int
Returns: int
Method signature (be sure your method is public): int toysToAdd(int p1, int
p2, int k)
In the signature:
- p1, p2 are the number of toys in each of the two 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.
NOTES
Topcoder will enforce the following input constraints:
p1 is between 1 and 5000, inclusive.
p2 is between 1 and 5000, inclusive.
k is between 1 and 20, inclusive.
It will always be possible to make player A lose.
EXAMPLES
toysToAdd(1,2,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,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,3,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.