nim game
closed account (STD8C542)
I've tried many codes but I'm still failing. I mainly tried this: if n = 155 and m = 47 then among 47, 94 and 141 select the best one to deduct from 155 but I still can't get around all test cases. There must be a simple logic behind this but nothing is striking to me at this moment. Any help is welcomed and I know this is an ongoing contest but just a push can help me. Thanks!
Last edited on
say that n<m
if m < 2n, then each move is unique and you may simply simulate the game (which is the euclid's gcd algorithm, so no problem with complexity)
else you may do m = m/n and play regular nim there to reach m = 1 or 2, then it's the above case.
if m < 2n, then each move is unique and you may simply simulate the game (which is the euclid's gcd algorithm, so no problem with complexity)
else you may do m = m/n and play regular nim there to reach m = 1 or 2, then it's the above case.
> I've tried many codes but I'm still failing.
Well you need to step back and analyse the problem on paper first.
Trying to wing it with some half-baked guess as to what the solution is will doom you to repeated failure.
Well you need to step back and analyse the problem on paper first.
Trying to wing it with some half-baked guess as to what the solution is will doom you to repeated failure.
> what do you mean by m=m/n?
suppose n=5 and m=103
instead of substracting by multiples of 5, you do m = 103/5 = 20 and remainder 3
play regular nim on the m=20 heap, and figure out if leaving m=8 is a winning or losing move.
> so if m < 2n then how do we use euclid's gcd?
implement the code to simulate the game
edit: ok, big mistake, let's try again
some definitions:
- winning/losing position: the player that moves now will win/lose
- winning move: ends in a losing position.
- losing move: ends in a winning position.
n < m, you need to figure out if the move that leaves m <- m%n is a winning or losing move
if m <- m%n is losing, then m <- m + m%n, if possible, is a winning move
¿how do you figure out wich one? simulate the game playing with the a <- a%b strategy (euclid's algorithm)
an example:
155 47
14 47
14 5
4 5
4 1
0 1 (end) whoever have to play now loses, so this is a losing position
now backtrack
[0 1] lose
[4 1] win
[4 5] lose
[14 5] win
[14 19] lose ***
[14 47] win
[51 47] lose ***
[155 47] win
that would be a perfect play, and the starter wins
the lines marked with *** show that the winning move was a <- a + a%b
suppose n=5 and m=103
instead of substracting by multiples of 5, you do m = 103/5 = 20 and remainder 3
play regular nim on the m=20 heap, and figure out if leaving m=8 is a winning or losing move.
> so if m < 2n then how do we use euclid's gcd?
implement the code to simulate the game
edit: ok, big mistake, let's try again
some definitions:
- winning/losing position: the player that moves now will win/lose
- winning move: ends in a losing position.
- losing move: ends in a winning position.
n < m, you need to figure out if the move that leaves m <- m%n is a winning or losing move
if m <- m%n is losing, then m <- m + m%n, if possible, is a winning move
¿how do you figure out wich one? simulate the game playing with the a <- a%b strategy (euclid's algorithm)
an example:
155 47
14 47
14 5
4 5
4 1
0 1 (end) whoever have to play now loses, so this is a losing position
now backtrack
[0 1] lose
[4 1] win
[4 5] lose
[14 5] win
[14 19] lose ***
[14 47] win
[51 47] lose ***
[155 47] win
that would be a perfect play, and the starter wins
the lines marked with *** show that the winning move was a <- a + a%b
Last edited on
| how is figuring out |
That is called strategy. "Nim is a mathematical game of strategy", see here for theory and variants: https://en.wikipedia.org/wiki/Nim
No matter what the move is ( a <- a + a%b or a <- a%b ) the numbers will eventually end up being the numbers of the simulation ( euclid's alg. ), so my idea was that the first one that has the option to choose from 2 moves ( a/b>1 if a>b, or b/a>1 if not ) will win. This obviously doesn't apply if a%b is 0 or b%a is 0, case in which the game ends.
If none of them has this option, the winner will be the one after the simulation.
Anything wrong with this reasoning ?
If none of them has this option, the winner will be the one after the simulation.
Anything wrong with this reasoning ?
Last edited on
Thanks for your help @neutralove, I was close to exact solution but your one is better and I found where my code computing wrong.
Last edited on
still showing wrong answer for the test cases except for the first test case
and also @neutralove method doesn't seem to work for all test cases like
101 and 13
ans:rich but according to neutralove its ari
can anyone help please .I am not understanding where i am doing mistake
this is my method
while(n!=0 && m!=0)
int picker=1;
if(n>m ) {
val=n/m;
val1=n%m;
n=m+val1;
if(val==1) {
n=n-m;
}
if(val==2) {
n=n%m;
}
picker++;
}
if(n<m){
same goes...
}
if(picker odd){
ans=ari;
}
else{
ans=rich
}
break
and also @neutralove method doesn't seem to work for all test cases like
101 and 13
ans:rich but according to neutralove its ari
can anyone help please .I am not understanding where i am doing mistake
this is my method
while(n!=0 && m!=0)
int picker=1;
if(n>m ) {
val=n/m;
val1=n%m;
n=m+val1;
if(val==1) {
n=n-m;
}
if(val==2) {
n=n%m;
}
picker++;
}
if(n<m){
same goes...
}
if(picker odd){
ans=ari;
}
else{
ans=rich
}
break
Last edited on
> and also @neutralove method doesn't seem to work for all test cases like
> 101 and 13
> ans:rich
the answer is ari, and that's what neutralove's algorithm says.
> this is my method
infinite loop at the start
unconditional break (outside of the loop)
counting two turns at once
vomiting the answer enven if there was no pick.
> 101 and 13
> ans:rich
the answer is ari, and that's what neutralove's algorithm says.
> this is my method
infinite loop at the start
unconditional break (outside of the loop)
counting two turns at once
vomiting the answer enven if there was no pick.
Topic archived. No new replies allowed.