Today while reading some posts on Facebook i found this puzzle on the ACM ICPC FB page, and i find it very easy because i know about impartial games which you can read about it on my blog here.
Here is the problem:
Here is my solution: each time we can pick one of the following combinations:
1. Red/Red
2. Red/Blue
3. Blue/Red
4. Blue/Blue
Last two cases will leave the box with same state, so we can use the following:
Lets define a state called solve(r, b, out) which defines the state of having r Red balls, B blue balls inside the box and out Red balls outside the box.
We can move from one state to another state by doing one of the moves described above.
What about base cases?
Here are the 2 base cases we have:
1. If we have 2 balls of the same color, we can move them and put a red ball in the box "Then the answer will be red"
2. If we have 2 balls of different colors, we can move them and return back the blue ball in the box "Then the answer will be blue"
Also we can use dynamic programming memoization to optimize our solution.
Here is my code for this problem. Enjoy it ;)
Here is the problem:
Here is my solution: each time we can pick one of the following combinations:
1. Red/Red
2. Red/Blue
3. Blue/Red
4. Blue/Blue
Last two cases will leave the box with same state, so we can use the following:
Lets define a state called solve(r, b, out) which defines the state of having r Red balls, B blue balls inside the box and out Red balls outside the box.
We can move from one state to another state by doing one of the moves described above.
What about base cases?
Here are the 2 base cases we have:
1. If we have 2 balls of the same color, we can move them and put a red ball in the box "Then the answer will be red"
2. If we have 2 balls of different colors, we can move them and return back the blue ball in the box "Then the answer will be blue"
Also we can use dynamic programming memoization to optimize our solution.
Here is my code for this problem. Enjoy it ;)
