Cod sursa(job #114945)

Utilizator snaked31Stanica Andrei snaked31 Data 16 decembrie 2007 09:45:47
Problema Multiplu Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.88 kb
#include <stdio.h>

#define nm 30

long long a, b, x, sol, i, lm, kkt;
long long A[nm];

void read()

{
	scanf("%lld %lld\n", &a, &b);
}


int ok(long long n)

{
	long long x = 0, i, pr = 1;
	for (i=n; i>0; --i)
	{
		x += (A[i] *pr);
		pr *=10;
	}
	if (x % a == 0 && x % b == 0 && x != 0)
		return 1;
	return 0;
}


long long mod(long long A[], long long B)  

{  
	long long i, t = 0;  
	for (i = A[0]; i > 0; i--)  
		t = (t * 10 + A[i]) % B;  
	return t;  
}  


int ok2(long long n)

{
	long long xx, yy, i, k = 0;
	long long B[nm], j;
	B[0] = n;
	for (i=n, j = 1; i>0; --i, ++j)
	{
		B[j] = A[i];
		if (A[i] == 1)
			++k;
	}
	xx = mod(B, a);
	yy = mod(B, b);
	if (xx == 0 && yy == 0 && k > 0)
		return 1;
	return 0;
}


void back(long long p, long long n)

{
	if (p > n)
	{
		if (ok(n))
		{
			long long i, pr;
			pr = 1;
			for (i=n; i>0; --i)
			{
				sol += (A[i] *pr);
				pr *=10;
			}
			x = 1;
		}
	}
	else
	{
		long long i;
		for (i=0; i<2 && x == 0; ++i)
		{
			A[p] = i;
			back(p+1, n);
		}
	}
}



void back2(int p, int n)

{
	if (p > n)
	{
		if (ok2(n))
		{
			A[0] = n;
			for (i=1; i<=n; ++i)
			{
				printf("%lld", A[i]);
			}
			printf("\n");
			x = 1;
		}
	}
	else
	{
		long long i;
		for (i=0; i<2 && x == 0; ++i)
		{
			A[p] = i;
			back2(p+1, n);
		}
	}
}


void solve()

{
	long long y = a, z = 0;
	lm = 0;
	while (y != 0)
	{
		lm ++;
		y/=10;
	}
	y = b;
	while (y != 0)
	{
		z ++;
		y/=10;
	}
	if (z < lm)
		lm = z;

	for (i=lm; i<20; ++i)
	{
		x = 0;
		back(1, i);
		if (x)
			break;
	}
	kkt = 0;
	if (sol == 0)
	{
		for (i=20; i<=30; ++i)
		{
			x = 0;
			back2(1, i);
			if (x)
			{
				kkt = 1;
				break;
			}
		}
/*		for (i=1; i<=A[0]; ++i)
		{
			printf("%lld", A[i]);
		}
		printf("\n");*/
	}
}


void write()

{
	if (!kkt)
		printf("%lld\n", sol);
}


int main()

{
	freopen("multiplu.in", "r", stdin);
	freopen("multiplu.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}