Cod sursa(job #3153845)

Utilizator iulia_morariuIulia Ela Morariu iulia_morariu Data 1 octombrie 2023 16:19:23
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

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

//ifstream fin("/Users/jdev/Documents/ProgrameInfoC++/Multiplu/multiplu.in");
//ofstream fout("/Users/jdev/Documents/ProgrameInfoC++/Multiplu/multiplu.out");

long long int a, b;

int cmmdc(int a, int b){
    int c = 0;
    while(b > 0){
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

struct poz{
    int mini, prec;
};

int main(){
    cin.tie(0);ios::sync_with_stdio(0);

    //1.

    //2.
    fin >> a >> b;

    //3.
    //cout << "a = " << a << " b = " << b << endl;
    //cout << "cmmdc = " << cmmdc(a, b) << endl;
    int cmmmc = (a / cmmdc(a, b)) * b;

    //cout << "cmmmc = " << cmmmc << endl;

    poz dp[cmmmc];

    for(int i = 0; i < cmmmc; i++){
        dp[i].mini = INT_MAX;
        dp[i].prec = -1;
    }

    dp[1].mini = 1;
    dp[1].prec = -1;

    queue<int> q;
    q.push(1);

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

        int r = (t * 10) % cmmmc;
        if(dp[r].mini > dp[t].mini + 1){
            dp[r].mini = dp[t].mini + 1;
            dp[r].prec = t;
        }
        if(r == 0) break;
        q.push(r);

        r = (t * 10 + 1) % cmmmc;
        if(dp[r].mini > dp[t].mini + 1){
            dp[r].mini = dp[t].mini + 1;
            dp[r].prec = t;
        }
        if(r == 0) break;
        q.push(r);
    }

    //cout << "facem din " << dp[0].mini << " cifre " << endl;

    string s;
    int poz = 0;
    for(int i = 0; i < dp[0].mini; i++){
        //cout << "poz = " << poz << endl;

        int op = 0;
        if( (dp[poz].prec * 10) % cmmmc != poz ) op = 1;

        s.insert(s.begin(), char( op + '0' ) );
        poz = dp[poz].prec;
    }

    fout << s << endl;




    return 0;
}