Cod sursa(job #1009355)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 12 octombrie 2013 22:26:55
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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;
}