Cod sursa(job #115324)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 decembrie 2007 12:11:08
Problema Multiplu Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 2.41 kb
#include<stdio.h>
#include<string.h>
long long int a,b,nz,nz1,aux,m,m0[20],m1[20],i,j,lc,lf;
char c0[10][20],c1[10][20],sc[10000000],sf[10000000];
void back(long long int poz);
void versol();
void ad(char *s1,char *s2);
void subs(char *s1,char *s2);
int main()
{
	FILE *f,*g;f=fopen("multiplu.in","r");g=fopen("multiplu.out","w");
	fscanf(f,"%lld%lld",&a,&b);
	while(a%2==0){nz1++;a/=2;}nz=(nz>nz1)?nz:nz1;nz1=0;
	while(a%5==0){nz1++;a/=5;}nz=(nz>nz1)?nz:nz1;nz1=0;
	while(b%2==0){nz1++;b/=2;}nz=(nz>nz1)?nz:nz1;nz1=0;
	while(b%5==0){nz1++;b/=5;}nz=(nz>nz1)?nz:nz1;
	m=a*b;lf=10000000;
	while(b){a=a%b;aux=a;a=b;b=aux;}
	m/=a;
	for(i=0;i<=9;i++) m0[i]=m*i;
	for(i=0;i<=8;i++)
	 { for(j=i;j<=9;j++)
	    if((i+m0[j])%10==0)break;
	  aux=m0[i];m0[i]=m0[j];m0[j]=aux;
	 }
	for(i=0;i<=9;i++)
	{ j=0;while(m0[i]){c0[i][j]='0'+(char)(m0[i]%10);m0[i]/=10;j++;}}
	c0[0][0]='0';
	for(i=0;i<=9;i++) m1[i]=m*i;
	for(i=0;i<=8;i++)
	 { for(j=i;j<=9;j++)
	    if((i+m1[j])%10==1)break;
	  aux=m1[i];m1[i]=m1[j];m1[j]=aux;
	 }
	for(i=0;i<=9;i++)
	{ j=0;while(m1[i]){c1[i][j]='0'+(char)(m1[i]%10);m1[i]/=10;j++;}}
	c1[1][0]='0';
	strcpy(sc,c1[0]);
	back(0);
	for(i=lf-1;i>=0;i--)
	  fprintf(g,"%c",sf[i]);
	 for(i=1;i<=nz;i++)
	  fprintf(g,"0");
	 fprintf(g,"\n");
	 fcloseall();
	 return 0;
}
void back(long long int poz)
{       char *qq,cc;
	long long int ok=1,v;
	if(strlen(sc)>lf)return;
	qq=&sc[poz];
	for(cc='2';cc<='9';cc++)
	 if(strchr(qq,cc)){ok=0;break;}
	if(ok){versol();return;}
	v=(long long int)(sc[poz]-'0');
	ad(qq,c1[v]);if(strlen(sc)<=lf)back(poz+1);subs(qq,c1[v]);
	ad(qq,c0[v]);if(strlen(sc)<=lf)back(poz+1);subs(qq,c0[v]);
}
void ad(char *s1,char *s2)
{       long long int ii;
	for(ii=0;;ii++)
	{ if(!s2[ii]) break;
	  s1[ii]+=s2[ii]-'0';
	  if(s2[ii]<'0')s2[ii]+='0';
	}
	for(ii=0;;ii++)
	{ while(s1[ii]>'9'){s1[ii]-=10;s1[ii+1]+=1;}
	  if(!s1[ii+1])break;
	  if(s1[ii+1]<'0')s1[ii+1]+='0';
	}
}
void subs(char *s1,char *s2)
{       long long int ii;
	for(ii=0;;ii++)
	{ if(!s2[ii]) break;
	  s1[ii]-=s2[ii]-'0';
	}
	for(ii=0;;ii++)
	{ if(!s1[ii])break;
	  while(s1[ii]<'0'){s1[ii]+=10;s1[ii+1]-=1;}
	}
	while(s1[ii]<='0'){s1[ii]=0;ii--;}
}
void versol()
{       long long int ok;
	lc=strlen(sc);
	if(lc>lf)return;
	if(lc<lf){lf=lc;strcpy(sf,sc);return;}
	ok=0;
	for(i=lf;i>=0;i--)
	{ if(sc[i]>sf[i])break;
	  if(sc[i]<sf[i]){ok=1;break;}
	}
	if(ok) strcpy(sf,sc);
}