Cod sursa(job #2774056)

Utilizator Theo14Ancuta Theodor Theo14 Data 9 septembrie 2021 17:14:20
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");

queue<int>coada;

int from[2000002],c,v[200002],st,dr;
//coada[2000002],

/*int frontelem()
{
    return coada[st];
}

void push(int nr)
{
    dr++;
    coada[dr]=nr;
}

void pop()
{
    st++;
}
*/
int cmmdc(int a, int b)
{
    if(a==0||b==0)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    int r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int cmmmc(int a, int b)
{
    return (a*b)/cmmdc(a,b);
}

void sol(int x)
{
    int k=0,y=0;
    while(y!=-1)
    {
        x=from[y];
        if((x*10)%c==y)
        {
            k++;
            v[k]=0;
        }
        else
        {
            k++;
            v[k]=1;
        }
        y=from[y];
    }
    for(int i=k; i>=1; i--)
        g<<v[i];
}

int main()
{
    int n,m,x,xx;
    f>>n>>m;
    c=cmmmc(n,m);
    if(c==1)
    {
        g<<1;
        return 0;
    }
    st=1;
    dr=0;
    coada.push(1);//push(1);
    from[1]=-1;
    while(14==14)
    {
        xx=coada.front();//xx=frontelem();
        coada.pop();
        x=xx*10;
        x=x%c;
        if(from[x]==0)
        {
            from[x]=xx;
            if(x==0)
                break;
            coada.push(x);
        }
        x=xx*10+1;
        x=x%c;
        if(from[x]==0)
        {
            from[x]=xx;
            if(x==0)
                break;
            coada.push(x);
        }
    }
    sol(0);
    return 0;
}