Cod sursa(job #2783637)

Utilizator DordeDorde Matei Dorde Data 14 octombrie 2021 20:19:10
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
ifstream f ("multiplu.in");
ofstream g ("multiplu.out");
int cmmdc (int a , int b){
    int r;
    while (b){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
vector <int> sol;
int const N = 3e6 + 1;
int edge [N] , t [N] , viz [N];

void out (int nr){
    int nod = nr;
    while (nod != -1){
        sol.push_back (edge [nod]);
        nod = t [nod];
    }
    reverse (sol.begin () , sol.end ());
    for(auto y : sol)
        g << y;
}
int main()
{
    int a , b;
    f >> a >> b;
    int x = a * b / cmmdc (a , b);
    viz [1] = 1;
    queue <int> q;
    q.push (1);
    t [1] = -1;
    edge [1] = 1;
    while (true){
        int nr = q.front ();
        q.pop ();
        int r1 = (nr * 10) % x;
        int r2 = (nr * 10 + 1) % x;
        if (! r1){
            sol.push_back (0);
            out (nr);
            exit (0);
        }
        if (! r2){
            sol.push_back (1);
            out (nr);
            exit (0);
        }
        if (! viz [r1]){
            q.push (r1);
            viz [r1] = 1;
            t [r1] = nr;
            edge [r1] = 0;
        }
        if (! viz [r2]){
            q.push (r2);
            viz [r2] = 1;
            t [r2] = nr;
            edge [r2] = 1;
        }
    }
    return 0;
}