Cod sursa(job #2266345)

Utilizator PredaBossPreda Andrei PredaBoss Data 22 octombrie 2018 16:33:23
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
#define pb push_back
#define DM 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
queue<pair<pair<int,int>,char> >Q;
int lcm,a,b;
bool viz[DM];
int mp[DM];
char rez[DM];
int main()
{
    fin>>a>>b;
    lcm = a*b/__gcd(a,b);
    Q.push({{1,1},1});
    while(!Q.empty()){
        int curr = Q.front().first.first;
        int where=Q.front().first.second;
        char r=Q.front().second;
        Q.pop();
        if(viz[curr]) continue;
        viz[curr]=true;
        rez[curr]=r;
        mp[curr]=where;
        if(!curr)
            break;
        int R0 = (curr*10)%lcm;
        int R1 = (curr*10+1)%lcm;
        if(viz[R0]) continue;
        if(R0==0)
        {
            rez[0]='0';
            mp[0]=curr;
            break;
        }
        Q.push({{R0,curr},'0'});
        if(viz[R1]) continue;
        if(R1==0)
        {
            rez[0]='1';
            mp[0]=curr;
            break;
        }
        Q.push({{R1,curr},'1'});
    }
    string ans;
    for(int i=0;i!=1;)
    {
        ans+=rez[i];
        i=mp[i];
    }
    ans+="1";
    reverse(ans.begin(),ans.end());
    fout<<ans;
    return 0;
}