- Prepare
- Algorithms
- Game Theory
- Game of Stones
- Discussions
Game of Stones
Game of Stones
+ 11 comments This is the O(1) solution based on the pattern.
for _ in xrange(input()): print ["First","Second"][input()%7 in [0,1]]
+ 1 comment The pattern emerges pretty quickly if you start from 1 stone and look at if the first player will win or lose with each stone you add.
SPOILER
You'll find that the first player will lose when the starting number of stones s is: 1,7,8,14,15,21,22... (i.e. when s % 7 < 2). With this knowledge in hand the code is trivial:
t = int(raw_input()) for _ in xrange(t): s = int(raw_input()) if s % 7 < 2: print 'Second' else: print 'First'
+ 1 comment Guys try it yourself for like 20 cases, on a paper! You will find out :P
+ 1 comment This game is composed of the repeating group of
LWWWWWL
Therefore the solution in Java is like this --> System.out.println(scanner.nextInt()%7<2?"Second":"First");Source: https://www.cs.umd.edu/~gasarch/COURSES/250/S15/nimnotes.pdf
+ 1 comment C++ Solution and Explaination:
At first I had tried to modulos N by 10 (n = n%10) and set the number of if statements for each possibility from 1 to 10 to determine the winner, I was completely wrong. So I purchased the Test Cases for TC #0 and noticed that the pattern repeated itself after the 7th entry, it would go "Second First First First First First Second" and after that the pattern was the same. So I realized the best answer was to check if n was equal or greater than 7 and if so modulus n by 7 (n = n % 7). If the remainder was 0, it meant n was equal to the 7th case of the pattern (7 or 14 for example) and Player 2 Wins or if the reminder was 1, it meant n was equal to the 1st case of the pattern (8 or 15 for example) and Player 2 wins, any other remainder meant Player 1 wins.
int main() { int t; cin >> t; for(int i = 0; i < t; i++){ int n; cin >> n; if(n >= 7) n %= 7; if(n == 0 || n == 1) cout << "Second" << endl; else cout << "First" << endl; } return 0; }
Sort 157 Discussions, By:
Please Login in order to post a comment