Cod sursa(job #1840422)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 4 ianuarie 2017 13:53:22
Problema Multiplu Scor 100
Compilator cpp Status done
Runda iconcurs7 Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

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

struct nod
{
    nod()
    {

    }
    nod(int tVal, int tFather)
    {
        val = tVal;
        father = tFather;
    }
    int val;
    int father;
};

int a, b, n;
bool viz[2000005];
vector<nod> q;

int cmmmc(int a, int b)
{
    return (a * b) / __gcd(a, b);
}

void afisare(nod x)
{
    stack<int> rasp;
    nod fth;
    while(x.father != -1)
    {
        fth = q[x.father];
        if((fth.val * 10) % n == x.val)
            rasp.push(0);
        else
            rasp.push(1);
        x = fth;
    }
    rasp.push(1);
    while(rasp.empty() == false)
    {
        out << rasp.top();
        rasp.pop();
    }
}

int main()
{
    in >> a >> b;
    if(a == 1 && b == 1)
    {
        out << 1;
        return 0;
    }
    n = cmmmc(a, b);
    int rest = 1 % n;
    q.push_back(nod(rest, -1));
    nod c;
    nod t;
    int first = 0;
    while(first < q.size())
    {
        c = q[first];

        rest = (c.val * 10) % n;
        if(viz[rest] == false)
        {
            viz[rest] = true;
            t = nod(rest, first);
            q.push_back(t);
            if(rest == 0)
            {
                afisare(t);
                break;
            }
        }

        rest = (c.val * 10 + 1) % n;
        if(viz[rest] == false)
        {
            viz[rest] = true;
            t = nod(rest, first);
            q.push_back(t);
            if(rest == 0)
            {
                afisare(t);
                break;
            }
        }

        ++first;
    }
    return 0;
}