Cod sursa(job #115558)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 16 decembrie 2007 12:58:10
Problema Multiplu Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 11-12 Marime 1.22 kb
#include <cstdio>
#include <string>
using namespace std;

#define MAX 2000000

inline long cmmdc(long a, long b) {
	while ( b ) { long r = a%b; a = b; b = r; }
	return a;
}

long a,b,c;
long R[MAX];	// R[i] = x => restul i se obtine din 1111..1 de x ori
string m;

string formeaza(long x, long y,long z) {
	string tmp(""); long i;
	for (i=x; i>y; --i)
		tmp+="1";
	for (i=y; i>z; --i)
		tmp+="0";
	for (i=z; i; --i)
		tmp+="1";
	return tmp;
}

int main() {
	fscanf(fopen("multiplu.in", "r"), "%ld %ld", &a, &b);

	c = a*b / cmmdc(a,b);

	long r,x,mx=0;
	for (r=1, x=1; r!=0 && R[r]==0; r=(r*10+1)%c, ++x)
    	R[r] = x, mx = (mx<r)?r:mx;
	if ( !r ) {
		R[0] = x;
		while ( x-- ) m += "1";
	} else {
		m = "1";
		while ( (--x)>R[r] ) m+="1";
		while ( x-- ) m+="0";
	}

	long i,j;
	for (i=1; i<=mx; ++i)
		if ( R[i] )
			for (j=1; j<=mx; ++j)
            	if ( R[j]<R[i] && R[j] ) {
	            	long nx=c-i+j;
    	        	if ( c-i+j<0 )
        	        	nx+=c;
                    else
                    	nx%=c;
                        

					if ( R[j] && nx<j && R[nx]) {
						string tmp = formeaza(R[i],R[j], R[nx]);
						if ( tmp<m )
							m = tmp;
					}
            }


	fprintf(fopen("multiplu.out","w"), "%s\n", m.c_str());
	return 0;
}