kevindu This is the O(1) solution based on the pattern.
for _ in xrange(input()): print ["First","Second"][input()%7 in [0,1]]
aaoferreira @kevindu do you mind to explain how did you get to that conclusion? thanks!
NikhilPathania input%7 defines the choice that first player can have after a series of steps. if value is 0 or 1
then player 1 loses as he has no choice, else if it is
2 then he will give 2, 3 then he will give 3, 4 then he will give 3, 5 then he will give 5, 6 then he will give 5.Clearly mod 7 is between 0-7, mod 7 is taken because max is 5 and min is 2, so at the climax of game atmost 7 cards are left
aaoferreira Thanks @Nikhil_Pathania !
dguai Isn't mod 7 between 0-6?
leom_hardt Yes, but
if( (x mod 7 == 1) OR (x mod 7 == 0))PRINT "Second" else PRINT "First"
lincolndu if( x mod 7 < 2 )PRINT "Second" else PRINT "First"
godaddy671 Is it right? I want to know more about this . I also take a help of Apple Support Canada to know this things. At the same time this site also helps me my Apple related issue. if anyone inteerested take a help of this site.
dorna_hassani I had the same question and still don't get the answer.
My solution was (dynamic programming approach):
private static String winner(int n) { String[] memory = new String[101]; Arrays.fill(memory, ""); return winner(n, memory); } private static String winner(int n, String[] memory){ if(n == 1){ return "Second"; } if(2 <= n && n <= 5){ return "First"; } if(memory[n] == ""){ if(winner(n - 5, memory) == "First" && winner(n - 3, memory) == "First" && winner(n - 2, memory) == "First"){ memory[n] = "Second"; } else{ memory[n] = "First"; } } return memory[n]; }which is longer than this solution and recursive but makes sense to myself. I'd like to understand the reasoning of the other solution, more specifically this sentence:
mod 7 is taken because max is 5 and min is 2, so at the climax of game atmost 7 cards are left.
ende76 It's proof by induction.
The hypothesis:
For n % 7 in [0, 1], the first player loses, otherwise the first player wins.The anchor:
Clearly, for 0 or 1 stones, the first player has no move, so he loses.
For any of 2, 3, 4, 5, or 6 stones, the first player can make a move that leaves 0 or 1 stones for the second player, so the first player wins.Induction step:
Now, for a given starting position n we assume that our hypothesis is true for all m < n.If n % 7 in [0, 1], we can only leave the second player with positions (n - 2) % 7 in [5, 6], (n - 3) % 7 in [4, 5], or (n - 5) % 7 = [2, 3], all of which mean – by induction – that the second player will be in a winning position. Thus, for n % 7 in [0, 1], the first player loses.
If n % 7 in [2, 3, 4, 5, 6], there's always a move to leave the second player with an m % 7 in [0, 1], thus – again by induction – forcing a loss on the second player, leaving the first player to win.
That concludes the proof.
The invariant is, that once a player A can force [0, 1] on player B, A can keep forcing that position, while B cannot force it on A.
dorna_hassani Thank you for the great response! Now I get the reason but don't think it's a solution I would think of intuitively. Hopefully after a while I'll get there.
ben_epstein I didn't think about it inductively (formally), although that is definitely a great way to think about it.
Another way is to test it out yourself until you see a pattern. You know that 2-6 will leave P1 as the winner, and you know that 7 will leave P1 as the loser. With this in mind:
Begin walking up one by one, deciding who would win given an input. 8 would leave P2 as the winner because P1 would subtract [2,3,5], leaving P2 with [3,5,6], all in the winning section.
Knowing that being at 7 or 8 cause that player to loose, figure out how the other player (P1) can 'force' P2 to get to 7 or 8 (Since P1 starts, she has the upper hand). You'll get to the point where you see that the next loosing numbers to be at are [14,15] which happen to be n%7[0,1] (As seen by the induction above). Hopefully then you will catch the pattern :)
salman_farsi Mind blown
AtharvaLohangade How did you choose number 7 ?
a7n007 [deleted]
mohitgupta943 [deleted]
c650Alpha This is crazy clever.
pariharyash6 smart solution
sttony 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
P2 P1 P1 p1 P1 P1 p2 p2 p1 p1 p1 p1 p1 p2 p2 p1 ...This will help understand. If n-5, n-3, n-2 can reach a P2 node, then n =P1, if not n=p2.
rochelly_fernan1 public static boolean isMultiple(int number){
double result = number % 7; double result2 = (number -1) % 7; if (result == 0 || result2 == 0) return true; else return false; }MobilityWins When 0(1) solution and 0("other solutions) I have no idea what that means, in my entire college degree (2 months from finishing) this has not been taught, what is the best source i can find teaching about runtime complexity solutions.
the_piranha Hi @MobilityWins , please refer to the link below. The first 6 videos in the playlist explain time complexity very beautifully.
https://www.youtube.com/playlist?list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0
lincolndu PHP solution
fscanf($_fp,"%d",$t); for($i=0;$i<$t;$i++){ fscanf($_fp,"%d",$n); echo ($n%7 <2 ) ? "Second\n" :"First\n"; }
wasuaje Python Version
n = int(input().strip()) for i in range(n): option = int(input().strip()) print("Second" if option % 7 in [0, 1] else "First")
sarathy_v_krish1 C++ solution :
string gameOfStones(int n) { if (n%7==0 || n%7==1) return "Second"; return "First"; }
NAklecha Guys try it yourself for like 20 cases, on a paper! You will find out :P
jpritcha3_14 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'
shivnshus My solution
int player2(int n){
if(n<2) return 1; return (player1(n-5)&&player1(n-3)&&player1(n-2));}
int player1(int n){
if(n<2) return 0; return (player2(n-5)||player2(n-3)||player2(n-2));}
int main() {
int n,t,i,j; scanf("%d",&t); for(int a0=0;a0<t;++a0){ scanf("%d",&n); i = player1(n); if(i==1) printf("First\n"); else printf("Second\n"); } return 0;}
noob_akshay //eliminate repeated calls with dp int gos(int n, int cur) { if(n less than 2) return cur; if(cur==0) return (gos(n-2,1) || gos(n-3,1) || gos(n-5,1) ); else return (gos(n-2,0) && gos(n-3,0) && gos(n-5,0) ); } Such a good problem :)
tao_zhang This game is composed of the repeating group of
LWWWWWLTherefore 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
pgmreddy True for repetition
sidpat Is there any actual theory behind this game?
Any other way to deduce the logic instead of just putting the numbers in and seeing the pattern?
Thanks, Sidpat
Pankaj_546Asked to answer Ya, there's a theory called- "Impartial Games" which deals with the cases when there are only two player and they either win or lose.
In face the problem is easy and can be coded with DP [O(n) solution], without finding the exact relationship (until the test cases are too large, you dont need the O(1) solution;IN CASE YOU NEED- still you can use the DP sol to get the table, and find the relation without hand coding every case ).
I first suggest you to Understand THIS problem. (as the same theory will be required many times). and then see the Impartial Games, as they can have many Extra Material you don't want.
Shafaet See the editorial to learn about winning-losing positions. If you don't understand how to deduce the logic, you won't be able to solve most game problems.
dmlerner Grundy numbers.
clivic The key to solve this problm is enumerate it out on a paper.
At first I thought wow when the n is big there were a lot of possibilities so how could it possible to have a fated loss or win. I was wrong.
reinaldo_rafael1 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; }
itbalachander Can you help me why if(n >=7) is used... I understood your code. But didnt get this condition statement .. Without that code work should fine ??
reinaldo_rafael1 Yes without it, it should work fine. It was there mainly so that I myself could understand it more clearly (Know why I used n%7 if I ever come back to the code and forget, although in retrospective I could've just written a comment.
yogeesh_pandey Tyipical case of dynamic programing.
This problem is biased to player one. if Any of the move chain exists which lead to player one to win player one to win.
ygongdev Surprised to see this marked as easy when a similar problem was marked as hard in another contest.
ParaLogia This problem is much more lenient, allowing for various naive implementations. The recent problem was more general, and the test cases/constraints were a lot wider, which prevented such solutions from passing. But I also think that was the easiest "hard" problem I ever saw.
Sort 95 Discussions, By:
Please Login in order to post a comment