Cod sursa(job #75635)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 4 august 2007 15:17:55
Problema Pavare2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
# include <stdio.h>
# include <string.h>

const long int MAXL=300;
const long int MAXN=100;
const long int BAZA=10;
const long int NCFB=1;
typedef struct NUMAR {long int len,v[MAXL+1];};
long int n,maxallowed[2];
NUMAR nr[MAXN+1][2][MAXN+1],nrt[MAXN+1][2][MAXN+1],sol,k;

long int min(long int a, long int b) {if (a>b) return b; return a;}
long int ncf(long int a) {if (a==0) return 1; long int sol=0;while (a) {sol++;a/=10;} return sol;}

////////////////////////
// NUMAR type handlers
////////////////////////

NUMAR numar_0,numar_1;

void init_nr()
{
numar_0.len=1;
numar_1.len=1;numar_1.v[1]=1;
}

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

void scade(NUMAR &sol, NUMAR a)
{
long int i;
for (i=1;i<=sol.len;i++)
	{
	sol.v[i]-=a.v[i];
	while (sol.v[i]<0)
		{
		sol.v[i+1]--;
		sol.v[i]+=BAZA;
		}
	}
while (sol.v[sol.len]==0) sol.len--;
if (sol.len==0) sol.len=1;
}

long int is_zero(NUMAR a) {if (a.len==1&&a.v[1]==0) return 1; return 0;}

void aduna(NUMAR a, NUMAR b, NUMAR &sol,long int clear)
{
long int i;
if (clear) sol=numar_0;
sol.len=a.len;if (b.len>a.len) sol.len=b.len;
for (i=1;i<=sol.len;i++)
	{
	sol.v[i]+=a.v[i]+b.v[i];
	if (sol.v[i]>=BAZA)
		{
		sol.v[i+1]+=sol.v[i]/BAZA;
		sol.v[i]%=BAZA;
		}
	}
while (sol.v[sol.len+1]!=0)  sol.len++;
}

////////////////////////
// MAIN handlers
////////////////////////

void citire()
{
FILE *f=fopen("pavare2.in","r");
fscanf(f,"%ld%ld%ld",&n,&maxallowed[0],&maxallowed[1]);
char buffer[1000];
fgets(buffer+1,1000,f);
fgets(buffer+1,1000,f);
k.len=strlen(buffer+1)-1;
long int i;
for (i=1;i<=k.len;i++)
	k.v[k.len-i+1]=(int)buffer[i]-48;
fclose(f);
}

void init_matrixes()
{
long int i,cf;
for (cf=0;cf<=1;cf++)
for (i=1;i<=maxallowed[cf];i++)
	{
	nr[i][cf][i]=numar_1;
	nrt[i][cf][i]=numar_1;
	}
}

void calculeaza()
{
long int l,cf,rep;
for (l=2;l<=n;l++)
	for (cf=0;cf<=1;cf++)
		for (rep=1;rep<=min(maxallowed[cf],l);rep++)
			{
			if (min(maxallowed[1-cf],l-rep))
			nr[l][cf][rep]=nrt[l-rep][1-cf][min(maxallowed[1-cf],l-rep)];
			if (rep==1) nrt[l][cf][rep]=nr[l][cf][rep];
			else aduna(nrt[l][cf][rep-1],nr[l][cf][rep],nrt[l][cf][rep],1);
			}
aduna(nrt[n][0][min(maxallowed[0],n)],nrt[n][1][min(maxallowed[1],n)],sol,1);
}

void scrie()
{
FILE *g=fopen("pavare2.out","w");
long int i,j;
fprintf(g,"%ld",sol.v[sol.len]);
for (i=sol.len-1;i>=1;i--)
	{
	for (j=ncf(sol.v[i]);j<NCFB;j++) fprintf(g,"0");
	fprintf(g,"%ld",sol.v[i]);
	fprintf(g,"\n");
	}
//
/*long int already=0,comp;
for (i=n;i>=1;i--)
	{
	if (already==maxallowed[0])
		{
		fprintf(g,"1");
		already=0;
		}
	else
		{
		comp=compara(k,nrt[i][0][min(maxallowed[0]-already,i)]);
		if (comp<=0)
			{
			fprintf(g,"0");
			already++;
			}
		else
			{
			fprintf(g,"1");
			scade(k,nrt[i][0][min(maxallowed[0]-already,i)]);
			already=0;
			}
		}
	}
fprintf(g,"\n");*/
for (i=1;i<=n;i++)
	{
	if (i>maxallowed[0]&&i%maxallowed[0]==1) fprintf(g,"1");
	else fprintf(g,"0");
	}
fprintf(g,"\n");
}

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