Cod sursa(job #155015)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 11 martie 2008 17:41:27
Problema Koba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
# include <stdio.h>

const long int MAXR=32;

typedef struct NEXT {int i,j,k;};
struct {NEXT next;long int sum;} c[10][10][10][MAXR+1];
long int n,t1,t2,t3;

void citire()
{
FILE *f=fopen("koba.in","r");
fscanf(f,"%ld%ld%ld%ld",&n,&t1,&t2,&t3);
t1%=10;t2%=10;t3%=10;
fcloseall();
}

void init()
{
long int i,j,k,row,i0,j0,k0;
for (i=0;i<=9;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
	{
	c[i][j][k][0].next.i=j;
	c[i][j][k][0].next.j=k;
	c[i][j][k][0].next.k=(i*j+k)%10;
	c[i][j][k][0].sum=k;
	}
for (row=1;row<=MAXR;row++)
for (i=0;i<=9;i++)
for (j=0;j<=9;j++)
for (k=0;k<=9;k++)
	{
	i0=c[i][j][k][row-1].next.i;
	j0=c[i][j][k][row-1].next.j;
	k0=c[i][j][k][row-1].next.k;
	c[i][j][k][row].next.i=c[i0][j0][k0][row-1].next.i;
	c[i][j][k][row].next.j=c[i0][j0][k0][row-1].next.j;
	c[i][j][k][row].next.k=c[i0][j0][k0][row-1].next.k;
	c[i][j][k][row].sum=c[i][j][k][row-1].sum+c[i0][j0][k0][row-1].sum;
	}
}

void scrie(long int sol)
{
FILE *g=fopen("koba.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

long int querry(long int i, long int j, long int k, long int n)
{
if (n==0) return 0;
int p=0;
while ( (1<<(p+1)) <= n) p++;
return c[i][j][k][p].sum+ querry(c[i][j][k][p].next.i,c[i][j][k][p].next.j,c[i][j][k][p].next.k,n-(1<<p));
}

int main()
{
citire();
init();
//printf("%d %d %d : %ld\n",c[9][7][3][2].next.i,c[9][7][3][2].next.j,c[9][7][3][2].next.k,c[9][7][3][2].sum);
long int sol=querry(t1,t2,t3,n-2);
scrie(sol+t1+t2);
return 0;
}