Cod sursa(job #2879990)

Utilizator tudor_costinCostin Tudor tudor_costin Data 29 martie 2022 11:57:26
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
queue<int> q;
int viz[2000005],previ[2000005];
int x;
void reconst(int y)
{
    if(y==1)
    {
        fout<<1;
        return;
    }
    reconst(previ[y]);
    if((previ[y]*10)%x==y)
    {
        fout<<0;
    }
    else
    {
        fout<<1;
    }
}
int main()
{
    int a,b;
    fin>>a>>b;
    if(b<=a)
    {
        for(int i=1; i<=b; i++)
        {
            if((a*i)%b==0)
            {
                x=a*i;
                break;
            }
        }
    }
    else
    {
        for(int i=1; i<=a; i++)
        {
            if((b*i)%a==0)
            {
                x=b*i;
                break;
            }
        }
    }
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        int r=q.front();
        ///cout<<r<<' '<<previ[r]<<'\n';
        if(r==0)
        {
            break;
        }
        q.pop();
        int r0=(r*10)%x;
        int r1=(r*10+1)%x;
        if(viz[r0]==0)
        {
            viz[r0]=1;
            previ[r0]=r;
            q.push(r0);
        }
        if(viz[r1]==0)
        {
            viz[r1]=1;
            previ[r1]=r;
            q.push(r1);
        }
    }
    reconst(0);
    return 0;
}