Cod sursa(job #2811359)

Utilizator octavi26octavian octavi26 Data 1 decembrie 2021 21:36:18
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
#define N 2000008

using namespace std;

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

int n;
int m;
int a, b;
bool viz[N];
int daddy[N];
int c[N];

void Citire()
{
    fin >> a >> b;
    m = a * b / __gcd(a, b);
}

vector<int> v;
queue<int> q;

void Afisare( int x )
{
    int i;
    while(x)
    {
        v.push_back( c[x] );
        x = daddy[x];
    }
    for( i=v.size() - 1; i >= 0; i-- )
        fout << v[i];
}

void Rezolvcare()
{
    int i;
    int x, y;
    q.push(1);
    daddy[1] = 0;
    viz[1] = 1;
    c[1] = 1;

    while( true )
    {
        n = q.front();
        x = (n * 10) % m;
        y = (n * 10 + 1) % m;
        q.pop();

        if (x == 0)
        {
            v.push_back(0);
            Afisare(n);
            return;
        }

        if (y == 0)
        {
            v.push_back(1);
            Afisare(n);
            return;
        }

        if (viz[x] == 0)
        {
            viz[x] = 1;
            daddy[x] = n;
            c[x] = 0;
            q.push(x);
        }

        if (viz[y] == 0)
        {
            viz[y] = 1;
            daddy[y] = n;
            c[y] = 1;
            q.push(y);
        }
    }
}

int main()
{
    Citire();
    Rezolvcare();
    fin.close();
    fout.close();
    return 0;
}