Cod sursă (job #111262)

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

using namespace std;

const int N=3010;
short int m[4][2*N];
char v[N];
int p[4],u[4],nv;

bool Maimic (int a, int b)
{
    if(u[a]<p[a])
        return 1;
    while(p[a]<=u[a] && m[a][p[a]]==0)
        p[a]++;
    while(p[a]<=u[a] && m[b][p[b]]==0)
        p[b]++;
    int i;

    if(u[a]-p[a]>u[b]-p[b])
        return 0;
    if(u[a]-p[a]<u[b]-p[b])
        return 1;
    for(i=0;i<=u[a]-p[a];i++)
    {
        if(m[a][p[a]+i]>m[b][p[b]+i])
            return 0;
        if(m[a][p[a]+i]<m[b][p[b]+i])
            return 1;
    }
    return 1;
}

void Scadere ()
{
    while(p[0]<=u[0] && m[0][p[0]]==0)
        p[0]++;
    while(p[3]<=u[3] && m[3][p[3]]==0)
        p[3]++;
    int i,t=0,c;
    //scade 3 din 0
    for(i=0;i<=u[3]-p[3];i++)
    {
        c=t+m[0][u[0]-i]-m[3][u[3]-i];
        t=0;
        if(c<0)
        {
            c+=10;
            t=-1;
        }
        m[0][u[0]-i]=c;
    }
    for(i=u[3]-p[3]+1;i<=u[0]-p[0];i++)
    {
        c=t+m[0][u[0]-i];
        t=0;
        if(c<0)
        {
            c+=10;
            t=-1;
        }
        m[0][u[0]-i]=c;
    }
    while(p[0]<=u[0] && m[0][p[0]]==0)
        p[0]++;
}

void Inmultire (int k, int a, int b)
{
    int i,t=0,c;
    //inmulteste a cu k si pune rezultatul in b
    p[b]=N+1;
    u[b]=N;
    if(u[a]<p[a] || k==0)
        return;
    while(p[a]<=u[a] && m[a][p[a]]==0)
        p[a]++;
    while(p[b]<=u[b] && m[b][p[b]]==0)
        p[b]++;

    for(i=0;i<=u[a]-p[a];i++)
    {
        c=t+m[a][u[a]-i]*k;
        t=c/10;
        c=c-t*10;
        p[b]--;
        m[b][p[b]]=c;
    }
    while(t>0)
    {
        c=t;
        t=c/10;
        c=c-t*10;
        p[b]--;
        m[b][p[b]]=c;
    }
    while(m[b][p[b]]==0)
        p[b]++;
}

void Radical ()
{
    int i,c;

    p[0]=p[1]=p[2]=p[3]=N+1;
    u[0]=u[1]=u[2]=u[3]=N;
    i=0;
    if(nv%2==0)
        i=1;
    for(;i<nv;i+=2)
    {
        //shifteaza m[0] cu doua cifre si adauga noua grupa
        m[0][u[0]+1]=v[i]-'0';
        m[0][u[0]+2]=v[i+1]-'0';
        u[0]+=2;

        //formeaza m[2]
        Inmultire(2,1,2);
        u[2]++;

        //gaseste c
        c=-1;
        do
        {
            c++;
            m[2][u[2]]=c;
            Inmultire(c,2,3);
        }
        while(c<10 && Maimic(3,0));

        c--;
        m[2][u[2]]=c;
        Inmultire(c,2,3);
        Scadere();
        u[1]++;
        m[1][u[1]]=c;
    }
}

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

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

    Radical();

    for(i=p[1];i<=u[1];i++)
        out<<m[1][i];
    return 0;
}