GAME THEORY IN COMPETITIVE PROGRAMMING
Game Theory in Competitive Programming Series: Part 4
Part 4 of Game Theory in CP — Game of Stones(Hackerrank)
Welcome to part 4 of this series, in case you have missed part 3, here is the link: https://medium.com/intellectually-yours/ticket-game-2f0a6c6e73b5
Hi peeps :) I brought a new game for algorithmic geeks who enjoy solving games rather than playing.
PROBLEM STATEMENT
Two players called P1 and P2 are playing a game with a starting number of stones. Player 1 always plays first, and the two players move in alternating turns. The game’s rules are as follows:
· In a single move, a player can remove either 2,3, or 5 stones from the game board.
· If a player is unable to make a move, that player loses the game.
Given the starting number of stones, find and print the name of the winner. P1 is named First and P2 is named Second. Each player plays optimally, meaning they will not make a move that causes them to lose the game if a winning move exists.
For example, if n=4, P1 can make the following moves:
· P1 removes 2 stones leaving 2. P2 will then remove 2 stones and win.
· P1 removes 3 stones leaving 1. P2 cannot move and loses.
P1 would make the second play and win the game.
PROBLEM LINK
INPUT FORMAT
The first line contains an integer t, the number of test cases.
Each of the next t lines contains an integer n, the number of stones in a test case.
Constraints
· 1<=n, t<=100
OUTPUT FORMAT
On a new line for each test case, print First if the first player is the winner. Otherwise print Second.
EXAMPLE
Sample Input
Sample Output
Explanation
In the sample, we have t=8 testcases.
If n=1, P1 can’t make any moves and loses the game.
If n=2, P1 removes 2 stones and wins the game.
If n=3, P1 removes 2 stones in their first move, leaving 1 stone on the board and winning the game.
If n=4, P1 removes 3 stones in their first move, leaving 1 stone on the board and winning the game.
If n=5, P1 removes all 5 stones from the game board, winning the game.
If n=6, P1 removes 5 stones in their first move, leaving 1 stone on the board and winning the game.
If n=7, P1 can make any of the following three moves:
1. Remove 2 stones, leaving 5 stones on the board. P2 then removes 5 stones, winning the game.
2. Remove 3 stones, leaving 4 stones on the board. P2 then removes 3 stones, leaving 1 stone left on the board and winning the game.
3. Remove 5 stones, leaving 2 stones on the board. P2 then removes the 2 remaining stones and wins the game.
All possible moves result in P2 winning.
If n=10, P1 can remove either 2 or 3 stones to win the game.
Using these Sample Inputs and their proper explanation as Hints try this problem on your own.
Some more Hints for your convenience:
HINT 1
Try to look for a pattern in this Q for which a particular player is winning.
HINT 2
If you can’t find the solution on your, I would highly recommend you to read the Q again with full focus and then try one last time before going ahead.
SPOILER ALERT !!
If you want to solve this on your own then STOP RIGHT NOW.
SOLUTION
This may seems like a hard problem to some, but believe me it is not. I hope you have tried your best to solve this problem. If you are successful then Hurray! But if you haven’t then don’t worry.
Here’s my logic
In problem, it’s given that Player 1 would always move optimally. So, Player 1 will win(considering that he is playing optimally) when at his turn, remaining stones are either 2 or 3 or 4 or 5 or 6. Because in this situation he will win by removing accordingly 2,3 or 5 stones. So, here if (stones%7)>1 then First player will win otherwise Second player.
That wasn’t too hard, was it? Most problems in life are simple if attempted with full focus!
CODE IMPLEMENTATION
That’s all for today! Stay tuned for Part 5 of Game Theory in CP !
