Cod sursa(job #2264753)

Utilizator PredaBossPreda Andrei PredaBoss Data 20 octombrie 2018 11:31:41
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 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>,int> >Q;
int lcm,a,b;
bitset<DM>viz;
map<int,int>mp;
map<int,bool>rez;
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;
        int r=Q.front().second;
        Q.pop();
        if(viz[curr]) continue;
        viz[curr] = 1;
        rez[curr]=r;
        mp[curr]=where;
        if(!curr)
            break;
        int R0 = (curr*10)%lcm;
        int R1 = (curr*10+1)%lcm;
        if(viz[R0]) continue;
        Q.push({{R0,curr},0});
        if(viz[R1]) continue;
        Q.push({{R1,curr},1});
    }
    string ans;
    for(int i=0;i!=1;)
    {
        if(rez[i])
            ans+="1";
        else
            ans+="0";
        i=mp[i];
    }
    ans+="1";
    reverse(ans.begin(),ans.end());
    fout<<ans;
    return 0;
}
/*#include <bits/stdc++.h>
#define pb push_back
#define DM 2000005
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

struct elm{
    string s;
    int r;
};

queue<elm>Q;
int lcm,a,b;
bitset<DM>viz;

int main()
{
    fin>>a>>b;
    lcm = a*b/__gcd(a,b);
    Q.push({"1",1});
    while(!Q.empty()){
        elm curr = Q.front();
        Q.pop();
        if(viz[curr.r]) continue;
        viz[curr.r] = 1;
        if(!curr.r){
            fout<<curr.s;
            return 0;
        }
        int R0 = (curr.r*10)%lcm;
        int R1 = (curr.r*10+1)%lcm;
        Q.push({curr.s+'0',R0});
        Q.push({curr.s+'1',R1});
    }
    return 0;
}*/