Cod sursă (job #111253)

#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;

        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]);
}


mazi nr;
mazi rad;
mazi partial;
mazi aux;
mazi what;

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

    gets(nr.v);

    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;
    }

    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]=j-10;
        partial.v[1]=j/10;
        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 (i<64){
        rad.v[0]=7;
    }
    else
    if (i<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 (aux.n==partial.n-1){
            j=partial.v[partial.n-1]*10+partial.v[partial.n-2];
            j=j/aux.v[aux.n-1];

            if (j>9) 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;
        }
        else
        if (aux.n==partial.n-2){
            j=partial.v[partial.n-1]*100+partial.v[partial.n-2]*10+partial.v[partial.n-3];
            j=j/aux.v[aux.n-1];

            if (j>9) 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;
        }
        else {
            rad=rad*10;
        }
    }

    print (rad);
    return 0;
}