My Weblog

Blog about programming and math

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.

using namespace std;
int G[1000010];

int main()

		int sum,ret;
		int count=1;
		//cout<<G[1]<<" ";
		for(int n=2;n<=200;n++) 
			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
			//cout<<G[n]<<" ";
			//if(count%34==0) {cout<<" "<<sum<<endl;sum=0;}
		for(int i=1;i<=(1000000%34);i++) if(G[68+i]==0) sum++;

November 1, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: