Cod sursa(job #160916)

Utilizator andyciupCiupan Andrei andyciup Data 17 martie 2008 12:21:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#define N 2000010
int v[N],coada[N],pred[N];
int a, b;
int gcd(int a,int b){
	int r=a%b;
	while(r){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}
void scrie(int x){
	if(pred[x]>=0)
		scrie(pred[x]);
	printf("%d",v[x]);
}
int main(){
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out", "w", stdout);
	scanf("%d", &a);
	scanf("%d", &b);
	long k;
	int i,p,u,rest=1;
	k=a*b/gcd(a,b);
	for(i=0;i<k;++i)
		v[i]=-1;
	p=u=0;
	coada[p]=1;
	v[1]=1;
	pred[1]=-1;
	while (p<=u){
		rest=coada[p]*10%k;
		if(v[rest]==-1)
		{
			v[rest]=0;
			pred[rest]=coada[p];
			coada[++u]=rest;
			if(rest==0){
				scrie(rest);
				printf("\n");
				return 0;
			}
		}
		rest=(coada[p]*10+1)%k;
		if(v[rest]==-1)
		{
			v[rest]=1;
			pred[rest]=coada[p];
			coada[++u]=rest;
			if(rest==0){
				scrie(rest);
				printf("\n");
				return 0;
			}
		}
		++p;
	}	
	return 0;
}