#include <stdio.h>
#include "time.h"

//Compute the code for column "a" plus m-multiple of column "b".
//Each column is coded by an integer from 0 to 124: 
//the code for column (a1,a2,a3) is 25 a1 + 5 a2 + a3.
unsigned int Add(unsigned int a, unsigned int m, unsigned int b)
{
	unsigned int t1,t2,t3;

	t1=(a/25 + b/25*m)%5;
	t2=(a%25/5 + b%25/5*m)%5;
	t3=(a%5 + b%5*m)%5;
	return(t1*25+t2*5+t3);
}

void main()
{
	const N=22;

	unsigned int i,j,k,l,code,inv,tnum,lostnum;
	unsigned int col[N], tcol[9];  
	bool Gen[N][5][125], adm[N+1][125];
	FILE *fp;
	time_t t;

	t = time(NULL);
	fp=fopen("out.txt","w");
	fclose(fp);
	fp=fopen("out.txt","a");
	fclose(fp);


	//The first four columns are 000,100,010,001.
	col[0]=0;	col[1]=25; col[2]=5; col[3]=1;

	//Calculate all j-column sums of the first four columns (0<=j<=4).

	//The j-column sums of the first column are all {0}.
	for (j=0;j<5;j++) 
	{
		Gen[0][j][0]=1;
		for (k=1;k<125;k++) Gen[0][j][k]=0;
	}
	
	//Compute the j-column sums recursively.
	for (i=1;i<4;i++)
	{

		//The j-column sums of first i columns contains that of first i-1 columns.
		for (j=0;j<5;j++)
		{
			for (k=0;k<125;k++) Gen[i][j][k]=Gen[i-1][j][k];
		}

		//New (j+l)-column sums are obtained from the j-column sums of
		//the first i-1 column and l multiple of column i.
		for (j=0;j<5;j++)
		{
			for (k=0;k<125;k++)
			{
				if (Gen[i-1][j][k])
				{
					for (l=1;l<5-j;l++)
						Gen[i][j+l][Add(k,l,col[i])]=1;
				}
			}
		}
	}

	//Compute the admissible code for the fifth column.
	//"Admissible" means that after adding new column, 
	//the sums of 5 columns can NOT be zero.
	//If "c" is a j-column sum of first four columns, 
	//then the fifth colum can NOT be j^(-1) multiple of "c".
	for (k=0;k<125;k++) adm[4][k]=1;

	for (j=1;j<5;j++)
	{
		if ((j==1) || (j==4)) 
			inv=j;
		else
			inv=5-j;

		for (k=0;k<125;k++)
		{
			if (Gen[3][j][k])
				adm[4][Add(0,inv,k)]=0;
		}
	}

	//Start from the fifth column to search for a counter-example.
	//Repeat until we have to change the 4th column or
	//we can get a counter-example.
	i=4; code=2; tnum=0; lostnum=0;
	while ((i>3) && (i<N))
	{

		//Search for an admissible code of the current column.
		while ((code<125) && (!(adm[i][code]))) code++;

		if (code<125)  //Indicate that there is at least one admissible code
		{
			
			col[i]=code; 

			//Compute the j-column sums. 

			for (j=0;j<5;j++)
			{	
				for (k=0;k<125;k++) Gen[i][j][k]=Gen[i-1][j][k];
			}

			if (i<5) //The 5th column may be choosen repeatly.
			{
				for (j=0;j<5;j++)
				{
					for (k=0;k<125;k++)
					{
						if (Gen[i-1][j][k])
						{
							for (l=1;l<5-j;l++)
								Gen[i][l+j][Add(k,l,col[i])]=1;
						}
					}
				}
			}
			else  //The 6th-22th column can be choosen only once.
			{
				for (j=0;j<4;j++)
				{
					for (k=0;k<125;k++)
					{
						if (Gen[i-1][j][k])
						{
							Gen[i][j+1][Add(k,1,col[i])]=1;
						}
					}
				}
			}

			i++; 

			if (i==N-1) 
			{
				fp=fopen("out.txt","a");

				tnum++;
				//Decide whether or not each vector appears four times
				if ((col[5]==col[8]) && (col[9]==col[12]) && (col[13]==col[16]) && (col[17]==col[20]))
				{
					for (k=0;k<6;k++) tcol[k]=col[k];
					tcol[6]=col[9]; tcol[7]=col[13]; tcol[8]=col[17];


					for (k=0;k<9;k++)
						fprintf(fp,"%d",tcol[k]/25);
					fprintf(fp,"\n");

					for (k=0;k<9;k++)
						fprintf(fp,"%d",tcol[k]%25/5);
					fprintf(fp,"\n");

					for (k=0;k<9;k++)
						fprintf(fp,"%d",tcol[k]%5);
					fprintf(fp,"\n");

					fprintf(fp,"\n");

				}
				else
				{
					for (k=0;k<N-1;k++)
						fprintf(fp,"%d%d%d,",col[k]/25,col[k]%25/5,col[k]%5);
					fprintf(fp,"---*\n");
					lostnum++;
				}
				fclose(fp);
			}


			//Calculate the minimal possible code for the new column.
			//Columns 4 and columns 5-22 are ordered respectively.
			//For i=4, code=col[i-1]+1; i=5, code=2; i=7..22, code=col[i-1]
			if (i<5) 
				code++;
			else
			{
				if (i==5) code=2;
			}

			//Calculate admissible codes for the new column

			for (k=0;k<125;k++) adm[i][k]=1;

			if (i<5)  //Columns 4 are allowed repeatly choosen.
			{
				for (j=1;j<5;j++)
				{
					if ((j==1) || (j==4)) 
						inv=j;
					else
						inv=5-j;
	
					for (k=0;k<125;k++)
					{
						if (Gen[i-1][j][k])
							adm[i][Add(0,inv,k)]=0;
					}
				}
			}
			else  //Columns 7-22 can be choosen only once.
			{
				for (k=0;k<125;k++)
				{
					if (Gen[i-1][4][k])
						adm[i][Add(0,4,k)]=0;
				}
			}
		}
		
		else //There is no admissible code, we have to change the code of column i-1.
		{
			i--; code=col[i]+1;
		}

	}

	fp=fopen("out.txt","a");
	fprintf(fp,"%ld\n",time(NULL)-t);

	if (i<=3) 
		//Test all values of col[i] and prove the conjectue.
		fprintf(fp,"The conjecture is ture!\n");
	else
	{
		//Output the counter-example.
		for (i=0;i<N;i++)
			fprintf(fp,"%d%d%d,",col[i]/25,col[i]%25/5,col[i]%5);
		fprintf(fp,"\n");
	}

	fprintf(fp,"The total number of nonzero 36-sequences is %d\n",tnum);
	fprintf(fp,"The number of exceptional 36-sequences is %d\n",lostnum);
	fclose(fp);
}