Cod sursă (job #310929)

/**
*   Bagam clasicul algoritm de radical.
*
*   Time Complexity : O(cifreN);
*
*   COROIAN DAVID, Satu Mare, ROMANIA
**/

#include <cstdio>

#include <cstring>

#define MAX_N 3000

using namespace std;

FILE *f, *g;

char s[MAX_N + 2];

int a[MAX_N + 2];

void readFile()
{
    f = fopen("sqrt.in", "r");

    fgets(s, MAX_N + 2, f);

    fclose(f);
}

void getN()
{
    a[0] = strlen(s);

    s[a[0] --] = 0;///'\n';

    int i;
    for(i = 0; i < a[0]; i ++)
        a[i + 1] = s[i] - '0';
}

void copyV(int a[], int b[])
{
    int i;
    for(i = b[0] + 1; i <= a[0]; i ++)
        a[i] = 0;

    for(i = 0; i <= b[0]; i ++)
        a[i] = b[i];
}

bool cmp(int a[], int b[])
{
    if(a[0] < b[0])
        return 0;

    if(a[0] > b[0])
        return 1;

    int i;
    for(i = 1; i <= a[0]; i ++)
    {
        if(a[i] < b[i])
            return 0;

        if(a[i] > b[i])
            return 1;
    }

    return 0;
}
/*
void aduna(int a, int b)
{
    int i;
    int mx = mxa(a[0], b[0]);

    if(b[0] > a[0])
    {
        for(i = a[0] + 1; i <= b[0]; i ++)
            a[i] = 0;
    }

    int t = 0;
    for(i = 1; i <= mx || (t != 0); i ++)
    {
        a[i] = a[i] + t + b[i];

        t = 0;

        if(a[i] > 9)
        {
            a[i] = a[i] - 10;

            t = 1;
        }
    }

    a[0] = i - 1;
}*/

int radical(int nr)
{
    int i = 0;
    int pas = 1 << 3;
    while(pas != 0)
    {
        if((i + pas) * (i + pas) <= nr)
            i += pas;

        pas /= 2;
    }

    return i;
}

void dreapta(int a[])
{
    int i;
    for(i = a[0] + 1; i >= 2; i --)
    {
        a[i] = a[i - 1];
    }

    a[1] = 0;

    a[0] += 1;
}

void stanga(int a[])
{
    int i;
    for(i = 1; i < a[0]; i ++)
    {
        a[i] = a[i + 1];
        a[i + 1] = 0;
    }

    a[0] -= 1;
}

void inmScalar(int a[], int nr)
{
    int t = 0;
    int i;
    for(i = a[0]; i >= 1 || (t > 0); i --)
    {
        t += a[i] * nr;

        a[i] = t % 10;

        t /= 10;
    }

    if(a[1] == 0)
        stanga(a);
}

int rez[(MAX_N >> 1) + 2];
int rez2[(MAX_N >> 1) + 2];

int rest[MAX_N + 2];

int tmp[MAX_N + 2];

void scrie(int a[])
{
    int i;
    for(i = 1; i <= a[0]; i ++)
        printf("%d", a[i]);

    printf("\n");
}

void scade(int a[], int b[])
{
    int i = a[0];
    int j = b[0];

    int t = 0;

    while(i > 0)
    {
        if(j > 0)
            t += b[j];

        a[i] = a[i] - t;

        t = 0;

        if(a[i] < 0)
        {
            t = 1;

            a[i] += 10;
        }

        i --;
        j --;
    }

    int zero = 1;
    while(a[zero] == 0 && zero <= a[0])
        zero ++;

    zero --;

    if(zero > 0)
    {
        int ramas = a[0] - zero;

        for(i = 1; i <= ramas; i ++)
        {
            a[i] = a[i + zero];

            a[i + zero] = 0;
        }

        a[0] = ramas;
    }
}

void getRez()
{
    int i = 0;
    if(a[0] & 1)
    {
        rez[0] = 1;
        rez[1] = radical(a[1]);

        rest[0] = 1;
        rest[1] = a[1] - rez[1] * rez[1];

        i = 1;
    }

    else
    {
        rez[0] = 1;
        rez[1] = radical(a[1] * 10 + a[2]);

        rest[0] = 1;

        int rst = a[1] * 10 + a[2] - rez[1] * rez[1];

        if(rst < 10)
            rest[1] = rst;

        else
        {
            rest[0] = 2;

            rest[2] = rst % 10;
            rest[1] = rst / 10;
        }

        i = 2;
    }

   // printf("++++++++++************** %d %d %d %d\n", rez[1], rest[1], rest[2], i);

    int n = a[0];

    i ++;
    for(; i < n; i += 2)
    {
        rest[++ rest[0]] = a[i];
        rest[++ rest[0]] = a[i + 1];

        int dig = 0;
        int pas = 1 << 3;

        copyV(rez2, rez);
        dreapta(rez2);
        inmScalar(rez2, 2);

        //printf("AVEM RESTUL si rez2\n");
       // scrie(rest);
       // scrie(rez2);

        while(pas != 0)
        {
            copyV(tmp, rez2);

            tmp[++ tmp[0]] = dig + pas;
            dreapta(tmp);
            inmScalar(tmp, dig + pas);

           // printf("AVEM TMP\n");
           // scrie(tmp);

            if(cmp(tmp, rest) < 1)
            {
                //printf("E MAI MIC DECAT REST\n");
                dig += pas;
            }

            pas /= 2;
        }

        copyV(tmp, rez2);

        tmp[++ tmp[0]] = dig;
        dreapta(tmp);
        inmScalar(tmp, dig);

        ////printf("++++++++++++++++++++++\n");
        //scrie(rest);
        //scrie(tmp);
        scade(rest, tmp);

       // printf("RAMANE\n");
       /// scrie(rest);
       // printf("AVEM CIFRA %d\n", dig);

        rez[++ rez[0]] = dig;
    }
}

void solve()
{
    getN();

    getRez();
}

void printFile()
{
    g = fopen("sqrt.out", "w");

    int i;
    for(i = 1; i <= rez[0]; i ++)
        fprintf(g, "%d", rez[i]);

    fprintf(g, "\n");
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}