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.

#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

November 1, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: