Cod sursă (job #123820)

#include <fstream>
#include <math.h>
using namespace std;
ifstream in("sqrt.in");
ofstream out("sqrt.out");
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;
    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;
    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)
    {
        m[0][u[0]+1]=v[i]-'0';
        m[0][u[0]+2]=v[i+1]-'0';
        u[0]+=2;
        Inmultire(2,1,2);
        u[2]++;
        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(){
    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;
}