Cod sursa(job #1253759)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 1 noiembrie 2014 19:21:03
Problema Multiplu Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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);
int main()
{
    int i, j, bun;
    fin>>a>>b;
    n = a*b;
    if(n==1){
        fout<<1;
        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;
        }
    }
}