Cod sursa(job #1436010)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 14 mai 2015 21:30:57
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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];
bitset<2000001> c;
bool used[2000001];
queue<int> Q;


void fa(int& r, int& x,const int cif)
{
    used[r] = true;
    //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;

    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(!used[rest1])
            fa(rest1, x, 0);
        if(!used[rest2])
            fa(rest2, x, 1);
    }
    return 0;
}


//FILE!!!