Cod sursa(job #1334055)

Utilizator andm99Andreea Mircescu andm99 Data 3 februarie 2015 20:52:44
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>
struct info
{ bool c;
    int r,t;
};
int cmmmc(int a,int b)
{
    int r,ca=a,cb=b;
    while(b){
      r=a%b;
      a=b;
      b=r;
      }
    return ca/a*cb;
}
info q[2000005];
int v[2000005],sol[1000005];
int main()
{
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    int a,b,m,p=1,r=1,i,u,r1;
    scanf("%d%d",&a,&b);
    m=cmmmc(a,b);
    p=1;
    q[p].c=1;
    r=1%m;
    q[p].r=1%m;
    v[1%m]=1;
    u=1;
    while(p<=u && q[p].r!=0){
      r1=(q[p].r*10)%m;
      if (v[r1]==0){
          u++;
          q[u].c=0;
          q[u].r=r1;
          q[u].t=p;
          v[r1]=1;
      }
      if  (q[u].r==0)
          break;
      r1=(q[p].r*10+1)%m;
      if (v[r1]==0){
          u++;
          q[u].c=1;
          q[u].r=r1;
          q[u].t=p;
          v[r1]=1;
      }
      if (q[u].r==0)
          break;
      p++;
    }
    int st,dr,alt,c=0;
    while(u){
      sol[++c]=q[u].c;
      u=q[u].t;
    }
    st=1;
    dr=c;
    while(st<dr){
      alt=sol[st];
      sol[st]=sol[dr];
      sol[dr]=alt;
      st++;
      dr--;
    }
    for(i=1;i<=c;i++)
        printf("%d",sol[i]);
return 0;
}