Cod sursa(job #2871253)

Utilizator db_123Balaban David db_123 Data 13 martie 2022 22:59:46
Problema Multiplu Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream cin ("multiplu.in");
ofstream cout ("multiplu.out");

vector<int> vR,vC;
queue<int> Q;

int a,b;
int mult;

int euclid(int a,int b){
    int modulo = a%b;
    while(b){
        modulo = a%b;
        a = b;
        b = modulo;
    }
    return a;
}
void display(){
    for(int i=0 ; i < vR.size();i++){
        cout << vR[i] << " ";
    }
    cout<<"\n";
    for(int i=0 ; i < vC.size();i++){
        cout << vC[i] << " ";
    }
    cout<<"\n";
}
void display1(int nr){
    if(nr!=1){
        display1(vR[nr]);
    }
    cout <<vC[nr];
}
int main(){

    int nr;
    cin >>a>>b;
    vR.resize(a*b+1);
    vC.resize(a*b+1);

    mult=a*b/euclid(a,b);

    nr =1;

    vR[1]=nr;
    vC[1]=nr;
    Q.push(nr);

    while(!Q.empty()){
        nr=Q.front();
        Q.pop();

        if (nr==0){
            break;
        }

        for(int i=0; i<=1; i++){
            int nrNew=(nr*10+i)%mult;
            if(vR[nrNew]==0){
                vR[nrNew]=nr;
                vC[nrNew]=i;
                Q.push(nrNew);
            }
        }
    }
    display1(0);
    //display();
    return 0;
}