# My Weblog

## 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;
}
```