Cod sursa(job #3306169)

Utilizator razvanmrt_06Mariuta Razvan razvanmrt_06 Data 8 august 2025 10:50:04
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Xmax = 2000005;

int A, B, X;
queue<int> Q;                /// in coada adaugam resturile prin X
vector<int> prv(Xmax, -1);   // prv[x] = restul cu care am ajuns in x
                             // prin adaugarea cifrei 0 sau 1

int cmmdc(int nr1, int nr2){
    while(nr1 != nr2){
        if(nr1 > nr2){
            nr1 -= nr2;
        }
        else{
            nr2 -= nr1;
        }
    }
    return nr1;
}

void reconst(int rest){
    if(rest == 1){
        fout << 1;
        return;
    }

    reconst(prv[rest]);

    if((prv[rest] * 10) % X == rest){
        fout << 0;
    }
    if((prv[rest] * 10 + 1) % X == rest){
        fout << 1;
    }
}

int main()
{
    fin >> A >> B;;
    X = (A * B) / cmmdc(A, B);

    prv[1] = 1;
    Q.push(1);
    while(!Q.empty()){
        int rest = Q.front();
        Q.pop();
        if(rest == 0){
            break;
        }

        int r0 = (rest * 10) % X;
        if(prv[r0] == -1){
            Q.push(r0);
            prv[r0] = rest;
        }

        int r1 = (rest * 10 + 1) % X;
        if(prv[r1] == -1){
            Q.push(r1);
            prv[r1] = rest;
        }
    }

    reconst(0);

    return 0;
}