Cod sursa(job #1781708)

Utilizator eragon0502Dumitrescu Dragos eragon0502 Data 17 octombrie 2016 11:39:38
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

using namespace std;

int c[2000000],st,dr;
int p[2000000];
int u[2000000];

void print(int x)
{
    if(x!=1)
        print(p[x]);
    printf("%d",u[x]);
}

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int x,y,pr,r,m,i;
    scanf("%d %d",&x,&y);
    pr=x*y;
    while(y>0)
    {
        r=x%y;
        x=y;
        y=r;
    }
    m=pr/x;
    c[1]=1;
    u[1]=1;
    i=1;
    st=0;
    dr=1;
    p[1] = 2000001;
    while(1)
    {
        ++st;
        if(p[c[st]*10%m]==0)
        {
            c[++dr]=c[st]*10%m;
            p[c[dr]]=c[st];
            u[c[dr]]=0;
        }
        if(c[dr]==0)
        {
            print(c[dr]);
            return 0;
        }
        if(p[(c[st]*10+1)%m]==0)
        {
            c[++dr]=(c[st]*10+1)%m;
            p[c[dr]]=c[st];
            u[c[dr]]=1;
        }
        if(c[dr]==0)
        {
            print(c[dr]);
            return 0;
        }
    }
    return 0;
}