Cod sursa(job #255096)

Utilizator swift90Ionut Bogdanescu swift90 Data 8 februarie 2009 17:06:36
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>
#define N 2000100
int nr[N],pred[N],coada[N];
int div(int a,int b){
	int rest=a%b;
	while(rest){
		a=b;
		b=rest;
		rest=a%b;
	}
	return b;
}
void scrie(int a){
	if(pred[a]>=0)
		scrie(pred[a]);
	printf("%d",nr[a]);
}
int main(){
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	int a,b,p,u,x,m;
	scanf("%d%d",&a,&b);
	m=(a*b)/div(a,b);
	for(p=0;p<m;++p)
		nr[p]=-1;
	p=u=0;
	coada[0]=1;
	nr[1]=1;
	pred[1]=-1;
	while(p<=u){
		x=(coada[p]*10)%m;
		if(nr[x]==-1){
			nr[x]=0;
			pred[x]=coada[p];
			coada[++u]=x;
			if(x==0){
				scrie(0);
				printf("\n");
				return 0;
			}
		}
		x=(coada[p]*10+1)%m;
		if(nr[x]==-1){
			nr[x]=1;
			pred[x]=coada[p];
			coada[++u]=x;
			if(x==0){
				scrie(0);
				printf("\n");
				return 0;
			}
		}
		++p;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}