Cod sursa(job #2490987)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 11 noiembrie 2019 16:42:04
Problema Multiplu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

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

int a , b;
bitset < 2000005 > mark;

struct Element
{
    int father , r;
    bool val;
}p , v[2000005];

queue < Element > c;

int cmmdc(int a , int b)
{
    int r;

    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

stack < bool > s;

void Print(int poz)
{
    do
    {
        s.push(v[poz].val);
        poz = v[poz].father;
    }while(v[poz].father);

    s.push(1);

    while(!s.empty())
    {
        g << s.top();
        s.pop();
    }

    exit(0);
}

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

    int m = a * b / cmmdc(a , b) , r , crest;
    mark[1] = 1;
    c.push({0 , 1 , 1});
    int cnt = 1 , nod_curr = 1 , new_r;
    v[1] = {0 , 1 , 1};

    while(!c.empty())
    {
        c.pop();
        r = v[nod_curr].r;

        new_r = r * 10 + 1;
        new_r %= m;

        if(!mark[new_r])
        {
            p.father = nod_curr;
            p.val = 1;
            p.r = new_r;
            v[++cnt] = p;

            if(!new_r)
                Print(cnt);

            mark[new_r] = 1;
            c.push(p);
        }

        new_r = r * 10;
        new_r %= m;

        if(!mark[new_r])
        {
            p.father = nod_curr;
            p.val = 0;
            p.r = new_r;
            v[++cnt] = p;

            if(!new_r)
                Print(cnt);

            mark[new_r] = 1;
            c.push(p);
        }

        ++nod_curr;
    }

    return 0;
}