Cod sursă (job #111260)

Utilizator avatar livlivi livia magureanu livlivi IP ascuns
Problemă Sqrt (clasele 9-10) Compilator cpp | 3,74 kb
Rundă Tema 13 clasele 9-10 2014/15 Status evaluat
Dată 27 ian. 2015 23:55:23 Scor 100
#include<cstdio>
#define MAX 3000
using namespace std;

int max(int a,int b){
    if (a>b) return a;
    return b;
}

struct mazi{
    int n;
    char v[MAX+1];

    mazi (){
        int i;
        for(i=0;i<=MAX;i++) this-> v[i]=0;
        this-> n=0;
    }

    mazi operator + (mazi ad){
        int r=0,i=0,m;

        m=max(ad.n,this-> n);

        while(i<m ||r!=0){
            r=this-> v[i] +ad.v[i] +r;

            ad.v[i]=r-10*(r>9);
            r=(r>9);
            i++;
        }

        ad.n=i;
        return ad;
    }

    mazi operator - (mazi sc){
        int r=0,i=0,m;

        m=sc.n;

        while(i<m ||r!=0){
            r=this-> v[i] -sc.v[i] -r;

            sc.v[i]=(r<0)*10+r;
            r=(r<0);
            i++;
        }

        while(i<this-> n){
            sc.v[i]=this-> v[i];
            i++;
        }

        sc.n=this-> n;
        while(sc.n>0 &&sc.v[sc.n-1]==0) sc.n--;

        return sc;
    }

    mazi operator * (const int scal){
        mazi rasp;
        int r=0,i=0,m;

        if (scal==0){
            rasp=mazi();
            return rasp;
        }

        m=this-> n;

        while(i<m ||r!=0){
            r=scal*this-> v[i] +r;

            rasp.v[i]=r%10;
            r/=10;
            i++;
        }

        rasp.n=i;
        return rasp;
    }

    bool operator < (mazi cmp){
        if (cmp.n < this-> n) return false;
        if (cmp.n > this-> n) return true;

        int i=cmp.n-1;
        while(i>0 &&this-> v[i]==cmp.v[i]) i--;

        return (this-> v[i] <= cmp.v[i]);
    }

};


void print(mazi &ceva){
    int i;
    for(i=ceva.n-1;i>=0;i--)
        printf ("%d",ceva.v[i]);

    printf ("\n");
}


mazi nr;
mazi rad;
mazi partial;
mazi aux;
mazi what;
//mazi sc;

int main(){
    freopen ("sqrt.in","r",stdin);
    freopen ("sqrt.out","w",stdout);
    int i,j,l;

    gets(nr.v);
    //sc.v[0]=1;
    //sc.n=1;

    nr.n=0;
    while(nr.v[nr.n]!=NULL){
        nr.v[nr.n]-='0';
        nr.n++;
    }

    for(i=0;i<nr.n/2;i++){
        j=nr.v[i];
        nr.v[i]=nr.v[nr.n-1-i];
        nr.v[nr.n-1-i]=j;
    }


    //while(nr.n!=0){
    if ((nr.n&1)==1){
        j=nr.v[nr.n-1];
        i=nr.n-2;
        partial.v[0]=j;
        partial.n=1;
    }
    else {
        j=nr.v[nr.n-1]*10+nr.v[nr.n-2];
        i=nr.n-3;
        partial.v[0]=nr.v[nr.n-2];
        partial.v[1]=nr.v[nr.n-1];
        partial.n=2;
    }

    if (j<4){
        rad.v[0]=1;
    }
    else
    if (j<9){
        rad.v[0]=2;
    }
    else
    if (j<16){
        rad.v[0]=3;
    }
    else
    if (j<25){
        rad.v[0]=4;
    }
    else
    if (j<36){
        rad.v[0]=5;
    }
    else
    if (j<49){
        rad.v[0]=6;
    }
    else
    if (j<64){
        rad.v[0]=7;
    }
    else
    if (j<81){
        rad.v[0]=8;
    }
    else {
        rad.v[0]=9;
    }

    rad.n=1;

    what=rad*rad.v[0];
    partial=partial-what;

    while(i>0){
        partial=partial*100;

        partial.v[1]=nr.v[i];
        partial.v[0]=nr.v[i-1];

        i-=2;

        aux=rad*2*10;

        if (partial<aux)
            j=0;
        else {
            j=partial.v[partial.n-1];
            l=0;

            while(aux.n+l!=partial.n &&l<3){
                l++;
                j=j*10+partial.v[partial.n-1-l];
            }

            j=j/aux.v[aux.n-1];

            if (j>9 ||l==3) j=9;
        }

        aux.v[0]=j;
        what=aux*j;
        while((what<partial)==0) {
            j--;
            aux.v[0]=j;
            what=aux*j;
        }

        rad=rad*10;
        rad.v[0]=j;

        partial=partial-what;
    }

    print (rad);

    /*nr=nr-sc;
    rad=mazi();
    what=mazi();
    aux=mazi();
    partial=mazi();*/
    //}

    return 0;
}