Cod sursa(job #1334033)

Utilizator andm99Andreea Mircescu andm99 Data 3 februarie 2015 20:30:37
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 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[r]=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[r]=1;
          }
      if (q[u].r==0)
          break;
      p++;
      }
    int st,dr,aux,c=0;
    while(u)
      {
      sol[++c]=q[u].c;
      u=q[u].t;
      }
    st=1;
    dr=c;
    while(st<dr)
      {
      aux=sol[st];
      sol[st]=sol[dr];
      sol[dr]=aux;
      st++;
      dr--;
      }
    for(i=1;i<=c;i++)
        printf("%d",sol[i]);
return 0;
}