Cod sursa(job #593109)

Utilizator elfusFlorin Chirica elfus Data 1 iunie 2011 13:04:26
Problema Multiplu Scor 100
Compilator cpp Status done
Runda pregatire_lot_juniori_1 Marime 0.74 kb
#include<stdio.h>
#define LMAX 2000000 + 2012

struct pozdy
{
	int c,r,last;
} q[LMAX];

bool f[LMAX];

void print(int x)
{
	if(q[x].last==0)
	{
		printf("1");
		return;
	}
	print(q[x].last);
	printf("%d",q[x].c);
}

int main()
{
	int A,B,r,a,b,C,c;
	
	freopen("multiplu.in","r",stdin);
	freopen("multiplu.out","w",stdout);
	
	scanf("%d%d",&A,&B);
	a=A; b=B;
	while(b)
	{
		r=a%b;
		a=b;
		b=r;
	}
	C=A*B/a;
	int p,u,val; p=u=1;
	q[1].c=1; q[1].r=1; q[1].last=0; f[1]=1;
	while(p<=u)
	{
		for(c=0;c<=1;c++)
		{
			val=(q[p].r*10+c)%C;
			if(!f[val])
			{
				f[val]=1;
				q[++u].c=c; q[u].r=val; q[u].last=p;
				if(val==0)
				{
					print(u);
					return 0;
				}
			}
		}
		p++;
	}
	return 0;
}