Cod sursa(job #1253802)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 1 noiembrie 2014 20:15:17
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
#define MAX 2000003
deque <int> q;
int n, t[MAX], a, b;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
void bfs(int nod);
bool isok(int x)
{
    while(x>0){
        if(x%10>1) return false;
        x = x/10;
    }
    return true;
}
int cmmdc(int a, int b){if(b==0)return a; return cmmdc(b, a%b);}
int main()
{
    int i, j, bun;
    fin>>a>>b;
    n = a/cmmdc(a, b)*b;
    if(isok(a) and a%b==0) n = a;
    if(isok(b) and b%a==0) n = b;
    if(isok(n)){
        fout<<n;
        return 0;
    }
    t[1] = -1;
    bfs(1);
    i = 0;
    q.clear();
    while(t[i]!=-1){
        if(t[i]*10%n==i) bun = 0;
        else bun = 1;
        q.push_front(bun);
        i = t[i];
    }
    q.push_front(1);
    while(!q.empty()){
        fout<<q.front();
        q.pop_front();
    }
    return 0;
}
void bfs(int nod)
{
    int i;
    q.push_back(nod);
    while(!q.empty()){
        nod = q.front();
        q.pop_front();
        if(t[nod*10%n]==0){
            t[nod*10%n] = nod;
            q.push_back(nod*10%n);
            if(nod*10%n==0) break;
        }
        if(t[(nod*10+1)%n]==0){
            t[(nod*10+1)%n] = nod;
            q.push_back((nod*10+1)%n);
            if((nod*10+1)%n==0) break;
        }
    }
}