## Project Euler Problem 306

Project Euler problem 306 hard problem for me although i was quite familiar with combinatorial games. First i tried to generated all the Grundy numbers up to 1000000 but running program for at least 5 hours did not produce any output. I printed couple of values for game and search online integer sequence. After couple of problem , finally solved.

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int G[1000010]; //http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation //http://www.research.att.com/~njas/sequences/A002187 int main() { int sum,ret; G[0]=G[1]=0; int count=1; //cout<<G[1]<<" "; for(int n=2;n<=200;n++) { ret=0; for(int i=0;i+1<=(n>>1);i++) ret=ret|(1<<(G[i]^G[n-2-i]));//set bit for each postion G[n]=__builtin_ctz(~ret);//find the position of set bit in negation //sum+=(G[n]>0?1:0); //cout<<G[n]<<" "; count++; //if(count%34==0) {cout<<" "<<sum<<endl;sum=0;} } sum=((1000000/34)-2)*5+13; for(int i=1;i<=(1000000%34);i++) if(G[68+i]==0) sum++; cout<<1000000-sum<<endl; }

Advertisements

No comments yet.

Advertisements

## Leave a Reply