Cod sursa(job #1816414)

Utilizator topala.andreiTopala Andrei topala.andrei Data 26 noiembrie 2016 14:07:13
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
queue<int> q;
int c[2000005];
int last[2000005];
int cmmdc(int x,int y)
{
    int r=x%y;
    while(r)
    {
        x=y;
        y=r;
        r=x%y;
    }
    return y;
}
void afisare(int u)
{
    if (last[u]==-1) return;
    afisare(last[u]);
    g<<c[u]-1;

}
int main()
{
    int A,B,nr,x,x1,x2,u;
    f>>A>>B;
    nr=A*B/cmmdc(A,B);
    c[1]=1;
    last[1]=-1;
    q.push(1);
    while(1)
    {
        x=q.front();
        q.pop();
        x1=(x*10)%nr;
        x2=(x*10+1)%nr;
        if (c[x1]==0) {c[x1]=1;last[x1]=x;q.push(x1);}
        if (c[x2]==0) {c[x2]=2;last[x2]=x;q.push(x2);}
        if (x1==0) {c[x1]=1;last[x1]=x;u=x1;break;}
        if (x2==0) {c[x1]=2;last[x2]=x;u=x2;break;}
    }
    g<<1;
    afisare(u);
}