Cod sursa(job #3122005)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 16 aprilie 2023 18:02:41
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

queue<int> q;
int prv[2000005], m;

void reconstruieste(int r)
{
    if (r == 1) {
        fout<<1;
        return;
    }

    int x = prv[r];
    reconstruieste(x);

    if ((x*10)%m == r) fout<<0;
    else fout<<1;
}

int main()
{
    int a, b, ca, cb;
    fin>>a>>b;
    ca = a, cb = b;

    while (b) {
        int r = a%b;
        a = b, b = r;
    }

    m = ca/a*cb;
    q.push(1);

    for (int i = 0; i < m; i++) prv[i] = -1;

    prv[1] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        if (x == 0) break;

        int x0 = (x*10)%m, x1 = (x*10+1)%m;

        if (prv[x0] == -1) q.push(x0), prv[x0] = x;
        if (prv[x1] == -1) q.push(x1), prv[x1] = x;
    }

    reconstruieste(0);
    return 0;
}