Cod sursa(job #30707)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 14 martie 2007 22:02:57
Problema Pavare2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
# include <stdio.h>
# include <string.h>

int n,a,b;
const int MAXN=100;
const int MAXL=33;

typedef struct {int len, nr[MAXL+1];} NUMAR;
NUMAR k;

NUMAR c[MAXN+1][2];

void citire()
{
FILE *f=fopen("pavare2.in","r");
fscanf(f,"%d%d%d",&n,&a,&b);
char s[MAXN];
fgets(s,100,f);
fgets(s,100,f);
s[strlen(s)-1]=s[strlen(s)];
k.len=strlen(s);
int i;
for (i=0;i<=k.len-1;i++)
	k.nr[i+1]=(int)s[i]-48;
fclose(f);
}

int min (int a, int b) {if (a>b) return b; return a;}

void init1(NUMAR &a)
{
a.len=1;
int i;
for (i=0;i<=MAXL;i++) a.nr[i]=0;
a.nr[1]=1;
}

void init0(NUMAR &a)
{
a.len=1;
int i;
for (i=0;i<=MAXL;i++) a.nr[i]=0;
}

NUMAR aduna(NUMAR a, NUMAR b)
{
int i;
NUMAR r;
init0(r);
for (i=1;i<=MAXL-1;i++) r.nr[i]=a.nr[i]+b.nr[i];
r.len=a.len;if (b.len>r.len) r.len=b.len;
i=1;
while (i<=r.len||r.nr[i]!=0)
	{
	if (r.nr[i]>=10) {r.nr[i+1]++;r.nr[i]%=10;}
	if (i>r.len) r.len=i;
	i++;
	}
return r;
}

void calculeaza()
{
int i,j;
init1(c[0][1]);
init1(c[0][0]);
for (i=1;i<=n;i++)
	{
	for (j=1;j<=min(a,i);j++) c[i][0]=aduna(c[i-j][1],c[i][0]);
	for (j=1;j<=min(b,i);j++) c[i][1]=aduna(c[i-j][0],c[i][1]);
	}
}

int maimaresauegal(NUMAR a, NUMAR b)
{
if (a.len<b.len) return 0;
if (a.len>b.len) return 1;
int i=a.len;
while (i)
	{
	if (a.nr[i]>b.nr[i]) return 1;
	if (a.nr[i]<b.nr[i]) return 0;
	i--;
	}
return 1;
}

NUMAR scade(NUMAR a, NUMAR b)
{
NUMAR r;
r=a;
int i;
for (i=1;i<=r.len;i++)
	r.nr[i]-=b.nr[i];
for (i=1;i<=r.len;i++)
	if (r.nr[i]<0)
		{
		r.nr[i]+=10;
		r.nr[i+1]--;
		}
while (r.nr[r.len]==0) r.len--;
return r;
}


void scrie()
{
FILE *g=fopen("pavare2.out","w");
//fprintf(g,"%lld\n",c[n][1]+c[n][0]);
NUMAR r;
r=aduna(c[n][1],c[n][0]);
int i=r.len;
while (i)
	{
	fprintf(g,"%d",r.nr[i]);
	i--;
	}
fprintf(g,"\n");
/// scrie solutia
int x=n,nr0=0,nr1=0,j;
while (x)
	{
	if (maimaresauegal(c[x][0],k)) {fprintf(g,"0");x--;nr0++;nr1=0;}
	else {fprintf(g,"1");k=scade(k,c[x][0]);x--;nr1++;nr0=0;}
	if (nr0)
		{
		init0(c[x][0]);
		for (j=1;j<=min(a-nr0,x);j++) c[x][0]=aduna(c[x-j][1],c[x][0]);
		}
	else
		{
		init0(c[x][1]);
		for (j=1;j<=min(b-nr1,x);j++) c[x][1]=aduna(c[x-j][0],c[x][1]);
		}
	}
fprintf(g,"\n");
fcloseall();
}

int main()
{
citire();
calculeaza();
scrie();
return 0;
}