Cod sursa(job #117183)

Utilizator megabyteBarsan Paul megabyte Data 20 decembrie 2007 21:28:04
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#define INF "multiplu.in"
#define OUF "multiplu.out"
#define NMAX 2000002
#define MIN(a,b) ((a<b)?(a):(b))
using namespace std;

int cmmdc(unsigned long long a,unsigned long long b)
{
         unsigned long long r;
         while(b!=0)
         {
                    r=a%b;
                    a=b;
                    b=r;
         }
         return a;
}


int que[NMAX]={0};
short t[NMAX]={0};
char s[NMAX]={0};
int main()
{
    int p,q,a,b,n,k,v;
    FILE *in,*out;
    in=fopen(INF,"r");
    out=fopen(OUF,"w");
    fscanf(in,"%d %d",&a,&b);
    
    if(a>b) p=cmmdc(a,b);
    else p=cmmdc(b,a);
    
    n=a*b/p;
//    printf("%d\n",n);
    
    p=1;q=1;
    que[1]=1;t[1]=1;

    while(p<=q)
    {
	    v=que[p];
	    a=(10*v)%n;
	    b=(a+1)%n;

	    if(!t[a]){que[++q]=a;t[a]=t[v]+1;}
	    if(a==0) break;	
	    
	    if(!t[b]){que[++q]=b;t[b]=t[v]+1;}
	    if(b==0) break;

	    ++p;
    }
    
 //   for(k=1;k<=q;++k) printf("%d %hd\n",que[k],t[que[k]]);
  //  printf("\n");
//	printf("%d %d\n",p,q);
    k=0;v=0;
    while(q>1)
    {
	    do
	    {
		    --q;
		    a=(10*que[q])%n;
		    b=(a+1)%n;
	    }while((t[v]-1)!=t[que[q]]||(v!=a&&v!=b));
		
//	    printf("%d %hd %d %hd\n",v,t[v],que[q],t[que[q]]);
	    if(a==v) s[++k]='0';
	    else s[++k]='1';

	    v=que[q];
		
    }

    fprintf(out,"1");
    while(k) fprintf(out,"%c",s[k--]);

    fclose(in);fclose(out);
    return 0;
}