Cod sursa(job #999531)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 20 septembrie 2013 17:33:58
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
int A,B,M;
bool viz[2000011];

struct coada{
    int v;
    int cif;
    int o;
};
coada c[1000011];

inline int cmmdc(int A,int B){
    register int r;
    r=(A>B?A:B),B=(A>B?B:A),A=r;
    while(A%B)
        r=A%B,A=B,B=r;
    return B;
}

inline int cmmmc(int A,int B){
    return (A*B)/cmmdc(A,B);
}

void afisare(int u){
    if(c[u].o>0)
        afisare(c[u].o);
    g<<c[u].cif;
}

int main(void){
    register int i,j;

    f>>A>>B;

    M=cmmmc(A,B);

    int p=1,u=1;
    c[1].v=1;
    c[1].cif=1;
    int val;
    while(p<=u){
        for(i=0;i<2;i++){
            val=(c[p].v*10+i)%M;
            if(!viz[val])
                c[++u].v=val,c[u].o=p,viz[c[u].v]=true,c[u].cif=i;
            if(val==0){
                //avem solutie
                afisare(u);
                return 0;
            }
        }
        p++;
    }
    f.close();
    g.close();
    return 0;
}