Cod sursa(job #1101434)

Utilizator TBLam99Tran Bach Lam TBLam99 Data 8 februarie 2014 14:48:28
Problema Multiplu Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<stdio.h>
#include<queue>
struct multiplu
{
            int x,bin;
};

int a,b,num,ca,cb,sol,r,tata,i,aux,rest;
int recon[2000001];
multiplu viz[2000001];
using namespace std;
int main()
{
            freopen("multiplu.in","r",stdin);
            freopen("multiplu.out","w",stdout);
            queue<int>q;
            scanf("%d%d",&a,&b);
            ca=a;
            cb=b;
            while(b!=0)
                {
                    r=a%b;
                    a=b;
                    b=r;
                }
            sol=ca*cb/a;
            aux=1%sol;
            viz[aux].bin=1;
            q.push(aux);
            while(q.empty()==0)
                {
                    tata=q.front();
                    rest=(tata*10)%sol;
                    if(rest==0)
                        {
                            aux=0;
                            recon[++num]=0;
                            while(viz[tata].x!=0)
                                {
                                    recon[++num]=viz[tata].bin;
                                    tata=viz[tata].x;
                                }
                            printf("1");
                            for(i=num;i>=1;--i)
                                printf("%d",recon[i]);
                            printf("\n");
                            return 0;
                        }
                    else
                        {
                            q.push(rest);
                            if(viz[rest].x==0)
                                {
                                    viz[rest].x=tata;
                                    viz[rest].bin=0;
                                }
                        }
                    rest=(tata*10+1)%sol;
                    if(rest==0)
                        {
                            aux=0;
                            recon[++num]=1;
                            while(viz[tata].x!=0)
                                {
                                    recon[++num]=viz[tata].bin;
                                    tata=viz[tata].x;
                                }
                            printf("1");
                            for(i=num;i>=1;--i)
                                printf("%d",recon[i]);
                            printf("\n");
                            return 0;
                        }
                    else
                        {
                            q.push(rest);
                            if(viz[rest].x==0)
                                {
                                    viz[rest].x=tata;
                                    viz[rest].bin=1;
                                }
                        }
                    q.pop();
                }
            return 0;
}