Cod sursa(job #3339385)

Utilizator PopRadGabPopescu Radu Gabriel PopRadGab Data 7 februarie 2026 17:50:16
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;

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

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

    int A,B;
    fin>>A>>B;

    int L=A/__gcd(A,B)*B;
    vector<int> sursa(L,-1),cifra(L,-1);
    vector<bool> vizitat(L,false);
    queue<int> q;

    int nods=1%L;
    q.push(nods);
    vizitat[nods]=true;
    cifra[nods]=1;
    sursa[nods]=-1;

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

        int r0=(crt*10)%L;
        if(!vizitat[r0]){
            vizitat[r0]=true;
            cifra[r0]=0;
            sursa[r0]=crt;
            q.push(r0);
        }

        int r1=(crt*10+1)%L;
        if(!vizitat[r1]){
            vizitat[r1]=true;
            cifra[r1]=1;
            sursa[r1]=crt;
            q.push(r1);
        }
        if(vizitat[0])
            break;
    }

    vector<int> raspuns;
    int r=0;
    while(r!=-1){
        raspuns.push_back(cifra[r]);
        r=sursa[r];
    }
    for(int i=0;i<raspuns.size()/2;i++)
        swap(raspuns[i],raspuns[raspuns.size()-i-1]);
    for(int i=0;i<raspuns.size();i++)
        fout<<raspuns[i];
    return 0;
}