Cod sursa(job #1333224)

Utilizator Eduard6421Eduard Gabriel Eduard6421 Data 2 februarie 2015 21:55:32
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>
#include<vector>
#define NMAX 2000005
using namespace std;

struct INFO
{
    bool c;
    int r,t;
};

INFO q[NMAX];
bool v[NMAX];
vector<int> sol;

int m,last,tata;
int a,b,i;

int main()
{
    FILE *fin,*fout;
    fin=fopen("multiplu.in","r");
    fout=fopen("multiplu.out","w");
    fscanf(fin,"%d%d",&a,&b);
    int x=a,y=b,r;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    m=x/a*y;

    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)
    {
        for(i=0; i<2; ++i)
        {
            y=(q[tata].r*10+i)%m;
            if(!v[y])
            {
                ++last;
                v[y]=true;
                q[last].c=i;
                q[last].r=y;
                q[last].t=tata;
            }
        }
        ++tata;
    }

    while(q[last].t!=last)
    {
        sol.push_back(q[last].c);
        last=q[last].t;
    }
    sol.push_back(1);
    i=sol.size()-1;
    for(i; i>=0; --i)
        fprintf(fout,"%d",sol[i]);
    return 0;
}