Cod sursa(job #1333184)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 2 februarie 2015 21:17:02
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<cstdio>
#include<vector>
#define NMAX 2000001
using namespace std;
int sol[NMAX];
struct INFO
{
    int c,r,t;
};
int lcm(int a,int b)
{

    int x=a,y=b,r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return (x/a)*y;
}
INFO q[NMAX];
int v[NMAX];
int main()
{
    int m,last,tata;
    int a,b,cnt=0;
    bool pas=false;
    FILE *fin,*fout;
    fin=fopen("multiplu.in","r");
    fout=fopen("multiplu.out","w");
    fscanf(fin,"%d%d",&a,&b);
    m=lcm(a,b);
    last=0;
    q[last].c=1;
    q[last].r=1%m;
    v[q[last].r]++;
    q[last].t=0;
    tata=0;
    while(q[last].r!=0)
    {
        if(!v[q[tata].r*10])
        {
            ++last;
            q[last].c=0;
            q[last].r=(q[tata].r*10+0)%m;
            q[last].t=tata;
            v[q[last].r]++;
        }
        if(q[last].r==0)
            break;
        if(!v[q[tata].r*10+1])
        {
            ++last;
            q[last].c=1;
            q[last].r=(q[tata].r*10+1)%m;
            q[last].t=tata;
            v[q[last].r]++;
        }
        ++tata;
    }
    int i=0;
    while(last!=q[last].t)
    {
        sol[i]=q[last].c;
        last=q[last].t;
        ++i;
    }
    sol[i]=1;
    for(i; i>=0; --i)
        fprintf(fout,"%d",sol[i]);
    return 0;
}