Cod sursa(job #1414333)

Utilizator avaspAva Spataru avasp Data 2 aprilie 2015 15:33:28
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<cstdio>
#include<queue>
using namespace std;
struct cmp{int rest,cif,poz;};
//queue<cmp>Q;
cmp coada[2000001];
cmp ales;
bool vc[2000001];
int ca,num,cb,a,b,res,rez,v[25];
int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    scanf("%d%d",&a,&b);
    ca=a;
    cb=b;
    while(cb!=0){
        res=ca%cb;
        ca=cb;
        cb=res;
    }
    num=(a*b)/ca;
    cmp str;
    str.rest=1;
    str.cif=1;
    str.poz=-1;
    if(num==1)
        printf("1");
    else{
        int ic,sf,pp=1;
        ic=sf=1;
        coada[ic]=str;
        while(pp==1){
            ales=coada[ic];
            //ad 0
            str.cif=0;
            str.poz=ic;
            str.rest=(ales.rest*10)%num;
            if(sf==6400){
                sf=6400;}
            if(str.rest==0){
                sf++;
                rez=sf;
                coada[sf]=str;
                pp=0;
            }
            else{
                if(vc[str.rest]==false){
                    sf++;
                    coada[sf]=str;
                    vc[str.rest]=true;
                }
                //ad 1
                str.cif=1;
                str.poz=ic;
                str.rest=(ales.rest*10 +1)%num;
                if(str.rest==0){
                    sf++;
                    rez=sf;
                    coada[sf]=str;
                    pp=0;
                }
                else
                if(vc[str.rest]==false){
                    sf++;
                    coada[sf]=str;
                    vc[str.rest]=true;
                }
            }
            ic++;
        }
        int i=rez,j=0;
        while(i>0){
            //printf("%d",coada[i].cif);
            v[++j]=coada[i].cif;
            i=coada[i].poz;
        }
        for(int i=j;i>=1;i--)
            printf("%d",v[i]);
    }
    return 0;
}