Cod sursă (job #111266)

#include <fstream>
#include <math.h>

using namespace std;

const int N=3008;
char w[N];
int first[4],last[4];
short int number[4][2*N];
int nr;

void Product (int q, int a, int b)
{
    int i,t=0,c;
    //inmulteste a cu q si pune rezultatul in b
    first[b]=N+1;
    last[b]=N;
    if(last[a]<first[a] || q==0)
        return;
    while(first[a]<=last[a] && number[a][first[a]]==0)
        first[a]++;
    while(first[b]<=last[b] && number[b][first[b]]==0)
        first[b]++;

    for(i=0;i<=last[a]-first[a];i++)
    {
        c=t+number[a][last[a]-i]*q;
        t=c/10;
        c=c-t*10;
        first[b]--;
        number[b][first[b]]=c;
    }
    while(t>0)
    {
        c=t;
        t=c/10;
        c=c-t*10;
        first[b]--;
        number[b][first[b]]=c;
    }
    while(number[b][first[b]]==0)
        first[b]++;
}

void Difference ()
{
    while(first[0]<=last[0] && number[0][first[0]]==0)
        first[0]++;
    while(first[3]<=last[3] && number[3][first[3]]==0)
        first[3]++;
    int i,t=0,c;
    //scade 3 din 0
    for(i=0;i<=last[3]-first[3];i++)
    {
        c=t+number[0][last[0]-i]-number[3][last[3]-i];
        t=0;
        if(c<0)
        {
            c+=10;
            t=-1;
        }
        number[0][last[0]-i]=c;
    }
    for(i=last[3]-first[3]+1;i<=last[0]-first[0];i++)
    {
        c=t+number[0][last[0]-i];
        t=0;
        if(c<0)
        {
            c+=10;
            t=-1;
        }
        number[0][last[0]-i]=c;
    }
    while(first[0]<=last[0] && number[0][first[0]]==0)
        first[0]++;
}

bool Smaller (int a, int b)
{
    if(last[a]<first[a])
        return 1;
    while(first[a]<=last[a] && number[a][first[a]]==0)
        first[a]++;
    while(first[a]<=last[a] && number[b][first[b]]==0)
        first[b]++;
    int i;

    if(last[a]-first[a]>last[b]-first[b])
        return 0;
    if(last[a]-first[a]<last[b]-first[b])
        return 1;
    for(i=0;i<=last[a]-first[a];i++)
    {
        if(number[a][first[a]+i]>number[b][first[b]+i])
            return 0;
        if(number[a][first[a]+i]<number[b][first[b]+i])
            return 1;
    }
    return 1;
}

void SQRT ()
{
    int i,c;

    first[0]=first[1]=first[2]=first[3]=N+1;
    last[0]=last[1]=last[2]=last[3]=N;
    i=0;
    if(nr%2==0)
        i=1;
    for(;i<nr;i+=2)
    {
        //shifteaza number[0] cu doua cifre si adauga noua grupa
        number[0][last[0]+1]=w[i]-'0';
        number[0][last[0]+2]=w[i+1]-'0';
        last[0]+=2;

        //formeaza number[2]
        Product(2,1,2);
        last[2]++;

        //gaseste c
        c=-1;
        do
        {
            c++;
            number[2][last[2]]=c;
            Product(c,2,3);
        }
        while(c<10 && Smaller(3,0));

        c--;
        number[2][last[2]]=c;
        Product(c,2,3);
        Difference();
        last[1]++;
        number[1][last[1]]=c;
    }
}

int main()
{
    ifstream in("sqrt.in");
    ofstream out("sqrt.out");

    int i;
    w[0]='0';
    in.getline(w+1,N);
    nr=0;
    while(w[nr])
        nr++;
    nr--;

    SQRT();

    for(i=first[1];i<=last[1];i++)
        out<<number[1][i];
    return 0;
}