Cod sursa(job #2784633)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 16 octombrie 2021 22:11:40
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

const int N = 2e6 + 1;
int a, b, m, tata[N], edge[N];
bool vis[N];
vector<int> ans;

void scrie(int nod){
    while(nod){
        ans.push_back(edge[nod]);
        nod = tata[nod];
    }

    reverse(ans.begin(), ans.end());
    for(int x: ans)
        g << x;
}

int main(){
    f >> a >> b;
    f.close();

    m = (a * b) / __gcd(a, b);
    tata[1] = 0, edge[1] = 1, vis[1] = 1;
    queue<int> q;
    q.push(1);
    while(true == true){
        int cmod = q.front();
        int x = (cmod * 10) % m;
        int y = (cmod * 10 + 1) % m;
        if(x == 0){
            ans.push_back(0);
            scrie(cmod);
            break;
        }

        if(y == 0){
            ans.push_back(1);
            scrie(cmod);
            break;
        }

        if(!vis[x]){
            vis[x] = 1;
            tata[x] = cmod;
            edge[x] = 0;
            q.push(x);
        }

        if(!vis[y]){
            vis[y] = 1;
            tata[y] = cmod;
            edge[y] = 0;
            q.push(y);
        }

        q.pop();
    }

    g.close();
}