Cod sursa(job #1097283)

Utilizator sandugavrilaGavrila Alexandru sandugavrila Data 3 februarie 2014 11:50:52
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>

using namespace std;
struct da
{
    bool c;
    int r,pred;
}q[2000000],temp;
int u=1,p=1;
 ofstream g("multiplu.out");

int cmmdc(int a,int b)
{
     while(a!=b)
    {
        if (a>b)
        a=a-b;
        if (b>a)
        b=b-a;
    }
    return a;
}

void sol()
{
    int v[100],n=0,i;
    while(u>=1)
    {
        v[n++]=q[u].c;
        u=q[u].pred;
    }
    for(i=n-1;i>=0;i--)
    g<<v[i];
}
bool viz[2000000];



int main()
{
    int a,b,m,i,r=0;
    ifstream f("multiplu.in");

    f>>a>>b;
    m=a*b/cmmdc(a,b);

    q[p].c=1;
    q[p].r=1;
    q[p].pred=0;
    viz[r]=1;

    while(p<=u)
    {
        for(i=0;i<=1;i++)
        {
            r=(q[p].r*10+i)%m;
            if(r==0)
            {
                temp.r=r;
                temp.c=i;
                temp.pred=p;
                viz[r]=1;
                q[++u]=temp;
                sol();
                return 0;
            }
            if(viz[r]==0)
            {
                temp.r=r;
                temp.c=i;
                temp.pred=p;
                viz[r]=1;
                q[++u]=temp;
            }

        }
        p++;
    }

    return 0;
}