Cod sursa(job #648152)

Utilizator vlad2901Vlad Berindei vlad2901 Data 13 decembrie 2011 04:30:00
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>

#define MMAX 2000000
using namespace std;

int A, B;
int c[MMAX], tata[MMAX], nr[MMAX], mod[MMAX];

void afis(int poz)
{
    if(tata[poz])
    {
        afis(tata[poz]);
    }
    printf("%d", nr[poz]);
}

int main()
{
    int mult, first, last, curent, r;
    int a, b;
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);

    scanf("%d %d", &A, &B);
    a = A;
    b = B;
    while(a != b)
    {
        while(a < b)
        {
            a += A;
        }
        while(b < a)
        {
            b += B;
        }
    }

    mult = a;
    nr[1] = 1;
    c[1] = 1;
    mod[1] = 1;
    first = 1;
    last = 1;

    while(first <= last)
    {
        curent = c[first++];
        r = (curent * 10) % mult;



        if(!mod[r]) //restul nu se afla deja in coada
        {
            mod[r] = 1;
            c[++last] = r;
            nr[last] = 0;
            tata[last] = first - 1;

        }

        if(r == 0)
        {
            break;
        }

        r = (curent * 10 + 1) % mult;




        if(!mod[r]) //restul nu se afla deja in coada
        {
            mod[r] = 1;
            c[++last] = r;
            nr[last] = 1;
            tata[last] = first - 1;
        }

        if(r == 0)
        {
            break;
        }
    }

    afis(last);



    return 0;
}