Cod sursa(job #1327472)

Utilizator dragos_musanMusan Dragos dragos_musan Data 26 ianuarie 2015 19:19:19
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <queue>
using namespace std;

const int NMAX = 2000000;

queue <int> q;
int c[NMAX], pred[NMAX];
bool sol[NMAX];

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

    r = a%b;

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

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

    int a,b,r,cmmmc, aux, p1, p0;

    f>>a>>b;

    cmmmc = a*b/cmmdc(a,b);

    q.push(1);
    c[1] = 1;
    pred[1] = 0;

    while(!q.empty())
    {
        aux = q.front();
        q.pop();

        p0 = (aux * 10) % cmmmc;
        p1 = (aux * 10 + 1) % cmmmc;

        if(pred[p0] == 0)
        {
            q.push(p0);
            c[p0] = 0;
            pred[p0] = aux;
        }
        if(pred[p1] == 0)
        {
            q.push(p1);
            c[p1] = 1;
            pred[p1] = aux;
        }

        if(p1 == 0 || p0 == 0)
            break;
    }

    int i = 0, j = 0;
    sol[j] = c[i];
    while(pred[i] != 0)
    {
        i = pred[i];
        j++;
        sol[j] = c[i];
    }

    for(; j>=0; j--)
        g<<sol[j];

    return 0;
}