Cod sursa(job #2263197)

Utilizator DavidLDavid Lauran DavidL Data 18 octombrie 2018 12:59:42
Problema Multiplu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
ifstream fi("multiplu.in");
ofstream fo("multiplu.out");

int a, b, lcm;
int curr;
vector <int> cif, ult, rez;
map <int, bool> avem;
queue < pair <int, int> > Q; /// (restul, momentul)

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

signed main()
{
    fi >> a >> b;
    lcm = a * b / gcd(a, b);

    Q.push({1, 0});
    avem[1] = 0;
    ult.pb(-1);
    cif.pb(1);

    int deacolo = -1;

    while (!Q.empty())
    {
        pair <int, int> nod = Q.front();
        Q.pop();

        int r = nod.first, t = nod.second;
        avem[r] = 0;

        if (r == 0)
        {
            deacolo = t;
            break;
        }

        /// bagam 0 la final
        if (!avem[r * 10 % lcm])
        {
            curr++;
            Q.push({r * 10 % lcm, curr});
            avem[r * 10 % lcm] = 1;
            ult.pb(t);
            cif.pb(0);
        }

        /// bagam 1
        if (!avem[(r * 10 + 1) % lcm])
        {
            curr++;
            Q.push({(r * 10 + 1) % lcm, curr});
            avem[(r * 10 + 1) % lcm] = 1;
            ult.pb(t);
            cif.pb(1);
        }
    }

    while (deacolo != -1)
    {
        rez.pb(cif[deacolo]);
        deacolo = ult[deacolo];
    }

    reverse(rez.begin(), rez.end());
    for (auto x: rez)
        fo << x;

    return 0;
}