Cod sursa(job #1332911)

Utilizator amina2002Abu Shanab Amina amina2002 Data 2 februarie 2015 16:07:52
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct info
{
    bool c;
    int r,t;

};
info q[2000005];
int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
bool f [200005];
int sol[2000005];

int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,n,p,u,i,nr=0,last;
    scanf("%d%d",&a,&b);
    n=a*b/cmmdc(a,b);
    q[1].c=1;
    q[1].r=1;
    q[1].t=0;
    p=1;
    u=1;
    int ini,r;
    f[1]=1;
    last=1;
    while(1)
    {
        for(i=p;i<=u;++i)
        {
            ini=q[i].r;
            r=(ini*10)%n;
            if(f[r]==0)
            {
                q[++last].c=0;
                q[last].t=i;
                q[last].r=r;
                f[r]=1;
            }
            if(r==0)
            {
                nr=0;
                i=last;
                while(q[i].t!=0)
                {
                    sol[++nr]=q[i].c;
                    i=q[i].t;
                }
                sol[++nr]=1;
                reverse(sol+1,sol+nr+1);
                for(i=1;i<=nr;++i)
                    printf("%d",sol[i]);
                    return 0;
            }
            r=(ini*10+1)%n;
            if(f[r]==0)
            {
                q[++last].c=1;
                q[last].t=i;
                q[last].r=r;
                f[r]=1;
            }
            if(r==0)
            {
                nr=0;
                i=last;
                while(q[i].t!=0)
                {
                    sol[++nr]=q[i].c;
                    i=q[i].t;
                }
                sol[++nr]=1;
                reverse(sol+1,sol+nr+1);
                for(i=1;i<=nr;++i)
                    printf("%d",sol[i]);
                    return 0;
            }

        }
        p=u+1;
        u=last;
    }
}