Cod sursa(job #1375117)

Utilizator SmitOanea Smit Andrei Smit Data 5 martie 2015 12:16:51
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>

using namespace std;

int a,b,m,q[2000004],pred[2000004];
bool viz[2000004],z[2000004],sol[50000];

inline void Citire()
{
    ifstream fin("multiplu.in");
    fin>>a>>b;
    fin.close();
}

inline int CMMMC(int x,int y)
{
    int r,x1,y1;
    x1=x;
    y1=y;
    r=x%y;
    while(r)
    {
        x=y;
        y=r;
        r=x%y;
    }
    return (x1*y1)/y;
}

inline void Solutie()
{
    int pr,ul,c,r,gata,x,i,poz,ind;
    c=CMMMC(a,b);
    pr=ul=1;
    q[pr]=1;
    z[1]=1;
    x=1;
    pred[1]=0;
    viz[x]=true;
    gata=0;
    while(!gata)
    {
        x=q[pr];
        pr++;
        x=x*10+0;
        r=x%c;
        if(r==0)
        {
            gata=1;
            //viz[r]=true;
            q[++ul]=r;
            z[ul]=false;
            pred[ul]=pr-1;
        }
        else
            if(viz[r]==false)
            {
               viz[r]=true;
                q[++ul]=x;
                z[ul]=false;
                pred[ul]=pr-1;
            }
        if(!gata)
        {
            x=x/10;
            x=x*10+1;
            r=x%c;
            if(r==0)
            {
                gata=1;
                //viz[r]=true;
                q[++ul]=r;
                z[ul]=true;
                pred[ul]=pr-1;
            }
            else
                if(viz[r]==false)
                {
                    viz[r]=true;
                    q[++ul]=x;
                    z[ul]=true;
                    pred[ul]=pr-1;
                }
        }
    }
    poz=ul;
    ind=0;
    while(poz!=0)
    {
        sol[++ind]=z[poz];
        poz=pred[poz];
    }
    ofstream fout("multiplu.out");
    for(i=ind;i>=1;--i)
        fout<<sol[i];
    fout<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Solutie();
    return 0;
}