Cod sursa(job #251810)

Utilizator IoannaPandele Ioana Ioanna Data 3 februarie 2009 13:39:51
Problema Multiplu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
typedef struct {int p,c;long r;}queue;
queue q[10000];
long a,b,m;
int sol[10000];


void read()
{
scanf("%ld%ld",&a,&b);
}

void cmmmc()
{
long long p;
long r;
p=a*b;
while (b)
      {
       r=a%b;
       a=b;
       b=r;
      }
m=p/a;
}

void numar(int k)
{
int pred;
pred=k;
while (pred)
      {
       sol[++sol[0]]=q[pred].c;
       pred=q[pred].p;
      }
}

void print()
{
int i;
for (i=sol[0];i>=1;i--)
    {
     printf("%d",sol[i]);
    }
printf("\n");
}

int find(long k,int l)
{
int i;
for (i=1;i<=l;i++)
    {
     if (q[i].r==k)
        return 1;
    }
 return 0;
}

int rez()
{
int st,dr;
long r;
st=dr=1;
q[st].c=1;
q[st].p=0;
q[st].r=1%m;
while (1)
      {
        //0
        r=(q[st].r*10)%m;
        if (!find(r,dr))
           {
            q[++dr].c=0;
            q[dr].p=st;
            q[dr].r=r;
            if (r==0)
                return dr;
           }
        //1
        r=(q[st].r*10+1)%m;
        if (!find(r,dr))
           {
            q[++dr].c=1;
            q[dr].p=st;
            q[dr].r=r;
            if (r==0)
                return dr;
           }
       st++;
      }
      
}



int main()
{
int k;
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
read();
cmmmc();
k=rez();
numar(k);
print();
return 0;
}