Cod sursa(job #1436004)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 14 mai 2015 21:23:23
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

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

int cmmdc(int a, int b)
{
    if(b == 0)
        return a;
    return cmmdc(b,a%b);
}

int t[2000001];
int nrc[2000001];
bitset<2000001> c;
queue<int> Q;

void fa(int& r, int& x,const int cif)
{


    nrc[r] = nrc[x] + 1;
    t[r] = x;
    c[r] = cif;
    Q.push(r);
}

void afis(int x)
{
    if(x != 1)
        afis(t[x]);
    fout<<c[x];
}

int main()
{
    int a, b;
    fin>>a>>b;
    int div = a*b/cmmdc(a,b);
    Q.push(1);
    c[1] = 1;
    nrc[1] = 1;
    bool found = false;
    int rest1, rest2;
    while(!Q.empty() && !found)
    {
        int x = Q.front();
        if(x == 0)
        {
            afis(x);
            found = true;
            continue;
        }
        Q.pop();

        rest1 = (x*10)%div;
        rest2 = (x*10+1)%div;
        if(nrc[x] + 1 < nrc[rest1] || nrc[rest1] == 0)
            fa(rest1, x, 0);
        if(nrc[x] + 1 < nrc[rest2] || nrc[rest2] == 0)
            fa(rest2, x, 1);
    }

    return 0;
}


//FILE!!!