Cod sursa(job #1097310)

Utilizator xtreme77Patrick Sava xtreme77 Data 3 februarie 2014 12:08:31
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#define MAX 2000007
using namespace std;
struct queue
{
    char c;
    int r,pred;
}q[MAX];
bool viz[MAX];
char rez[MAX];
int cmmdc(int a,int b);
void solve();
int p,u,a,b,m,r;
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d",&a,&b);
    queue temp;
    m=cmmdc(a,b);
    m=(a*b)/m;
    p=u=1;
    q[p].c=1;
    q[p].r=1;
    q[p].pred=0;
    viz[1]=1;
    while(p<=u)
    {
            r=(q[p].r*10+0)%m;
            if(viz[r]==0)
            {
                temp.c=0;
                temp.r=r;
                temp.pred=p;
                viz[r]=1;
                q[++u]=temp;
            }
            if(r==0){
            solve();
            return 0;
            }
            r=(q[p].r*10+1)%m;
            if(viz[r]==0)
            {
                temp.c=1;
                temp.r=r;
                temp.pred=p;
                viz[r]=1;
                q[++u]=temp;
            }
            if(r==0){
            solve();
            return 0;
            }
            p++;
    }
    return 0;
}
int cmmdc(int a,int b)
{
    if(!b)return a;
    return cmmdc(b,a%b);
}
void solve()
{
    int k=1,i;
    while(u)
    {
        rez[k++]=q[u].c;
        u=q[u].pred;
    }
    for(i=k-1;i>=1;--i)printf("%d",rez[i]);
    printf("\n");
}