Cod sursa(job #960681)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 10 iunie 2013 22:46:05
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb

#include <fstream>
using namespace std;

long A,B,C;

long cmmdc(long a,long b)
{
    while (b != 0)
    {
        long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long cmmmc(long a,long b)
{
    return a * b / cmmdc(a,b);
}

long Cifre[2000005];
long Prev[2000005];

long Queue[2000005];
long PushPos;
long PopPos;

void Push(long a)
{
    Queue[PushPos] = a;
    PushPos += 1;
}

long Pop(void)
{
    PopPos += 1;
    return Queue[PopPos - 1];
}

long Empty(void)
{
    return PushPos == PopPos;
}

int main(void)
{
    fstream fin("multiplu.in",ios::in);
    fstream fout("multiplu.out",ios::out);

    fin >> A >> B;
    C = cmmmc(A,B);

    Cifre[1] = 1;
    Prev[1] = -1;

    PushPos = 0;
    PopPos = 0;

    Push(1);
    while (Empty() == 0)
    {
        long v = Pop();
        if (v == 0)
        {
            while (Prev[v] != 0)
            {
                fout << Cifre[v];
                v = Prev[v];
            }
            break;
        }

        long v1,v2;
        v1 = (v * 10 + 0) % C;
        v2 = (v * 10 + 1) % C;

        if (Prev[v1] == 0)
        {
            Prev[v1] = v;
            Cifre[v1] = 0;
            Push(v1);
        }

        if (Prev[v2] == 0)
        {
            Prev[v2] = v;
            Cifre[v2] = 1;
            Push(v2);
        }
    }

    fin.close();
    fout.close();
    return 0;
}