#include <stdio.h>

int kiir(mit,hova)
    long long int mit;
    char *hova;
	{
	char tmp[21];
	int i;
	if(!mit){sprintf(hova,"0");return(0);}
	i=0;
	while(mit){
		tmp[i]=(mit%10)+'0';
		mit/=10;
		i++;
		}
	while(i){
		i--;
		*hova=tmp[i];
		hova++;
		}
	*hova=0;
	}

void main(int argc, char *argv[]){

	const nn=30; /* n az iteracio melysege */
	const NN=59049; /* N=3^(n/3) a mertek lehetseges ertekeinek szama*/
	int n;
	int i[nn+1],M[nn+1],N,j,k,max;
	long long int total,a[NN+1];
	char szoveg[21];

	if (argc<2){
		fprintf(stderr,"Az iteracio melyseget kerem parameternek!\n");
		exit(-1);
		}
	n=atoi(argv[1]);
		if(n<3){
		    fprintf(stderr,"A parameter legyen legalabb 3.\n");
		    exit(-1);}	
		if(n>30){
		    fprintf(stderr,"A parameter legyen legfeljebb 30.\n");
		    exit(-1);}	
		if((n%3)==0){N=1;for(k=3;k<=n;k+=3)N*=3;}
		if((n%3)==1){N=4;for(k=7;k<=n;k+=3)N*=3;}
		if((n%3)==2){N=2;for(k=5;k<=n;k+=3)N*=3;}
	printf("n=%d N=%d\n",n,N);
	total=0;max=0;
	for(k=0;k<=n;k++){i[k]=0;M[k]=1;}
	for(k=0;k<=N;k++)a[k]=0;
	i[0]=5;j=n;
	while(j){
/*
		printf("\t%d %d %d %d %d\n",i[1],i[2],i[3],i[4],j);
		printf("\t%d %d %d %d %d\n",M[1],M[2],M[3],M[4],j);
*/
		if((i[j]==2)&&(i[j-1]==0)){
			i[j]=0;
			i[j-1]=1;
			M[j]=M[j-1]+M[j-2];M[j-1]=M[j-2];
			}
		  else{if(i[j]==3){
			i[j]=0;
			j--;
			i[j]++;
			M[j]=M[j-1];
			}
		  else{
			while(j<n){M[j+1]=M[j];j++;}
/*
			for(k=1;k<=n;k++)printf("%d ",i[k]);
			printf("   %d\n",M[n]);
*/
			total+=M[n];if(M[n]>max)max=M[n];
			a[M[n]]++;
			i[n]++;
			M[n]=M[n-1];
			}
			}
		}
	kiir(total,szoveg);
	printf("osszesen %s\n",szoveg);
	printf("legnagyobb %d\n",max);
	if(max!=N)printf("GAZ VAN: legnagyobb <> N !\n");
	for(k=1;k<=N;k++){
		kiir(a[k],szoveg);           
		printf("%d %s\n",k,szoveg);
		}
	}