We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Zero-Move Nim
  5. Discussions

Zero-Move Nim

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 17 Discussions, By:

votes

Please Login in order to post a comment

  • levpolka
    3 years ago+ 1 comment

    (If someone is struggling) Caution, spoiler!

    Create two arrays: g1 and g2. Let g1 contains grundy numbers of piles with zero-move used, and g2 contains those without. See the link between these two arrays.

    Real spoiler!

    g1[0]=0

    g1[1]=mex{g1[0]}=1

    g1[2]=mex{g1[0], g1[1]}=2

    ...

    g2[0]=0

    g2[1]=mex{g1[1], g2[0]}=2

    g2[2]=mex{g1[2], g2[0], g2[1]}=1

    ...

    6|
    Permalink
  • meghanto20
    2 years ago+ 0 comments
    from functools import reduce
    def zeroMoveNim(p):
        p=[i-1+2*(i%2) for i in p]
        return 'W' if reduce((lambda x,y:x^y),p) else 'L'
    
    2|
    Permalink
  • sachidanandapat2
    3 years ago+ 0 comments

    Refer something as grundy numbers in game theory. grundy numbers are 1->2 2->1 3->4 4->3 .. .. consider left side as pile size and right as grundy number .Create an array of grundy numbers and perform xor.Then its same as nim.

    2|
    Permalink
  • RAKESH_MAURYA
    3 years ago+ 2 comments
    for t in range(int(input())):
        input()
        y = 0
        for z in input().split():
            x = int(z)
            if x%2:
                x+=1
            else:
                x-=1
            y^=x
        if y:
            print ("W")
        else:
            print ("L")
    
    2|
    Permalink
  • hunta55555
    3 years ago+ 0 comments
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<ll> vl;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    
    typedef int _loop_int;
    #define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
    #define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
    #define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
    
    #define DEBUG(x) cout<<#x<<": "<<x<<endl
    #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
    #define ALL(a) (a).begin(),(a).end()
    
    #define CHMIN(a,b) a=min((a),(b))
    #define CHMAX(a,b) a=max((a),(b))
    
    // mod
    const ll MOD = 1000000007ll;
    #define FIX(a) ((a)%MOD+MOD)%MOD
    
    // floating
    typedef double Real;
    const Real EPS = 1e-11;
    #define EQ0(x) (abs(x)<EPS)
    #define EQ(a,b) (abs(a-b)<EPS)
    typedef complex<Real> P;
    
    void solve(){
      int n;
      scanf("%d",&n);
      int x = 0;
      while(n--){
        int v;
        scanf("%d",&v);
        if(v&1)v++;
        else v--;
        x ^= v;
      }
      puts(x==0?"L":"W");
    }
    
    int main(){
      int g;
      scanf("%d",&g);
      while(g--)solve();
      return 0;
    }
    
    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature