Cod sursă (job #111277)

#include<stdio.h>

#define MAXX 5000

FILE *in, *out;

char v[MAXX], dec[MAXX], predec[MAXX], dscz[MAXX];
int nrv, nrdec, nrpredec, nrdscz;

int clean(char a[], int lunga)
{
    int i;

    i = lunga - 1;
    while(a[i] == 0 && i > 0) {
        i = i - 1;
        lunga = lunga - 1;
    }

    return lunga;
}

int cmp(char a[], char b[], int lunga, int lungb)
{
    int i;

    lunga = clean(a, lunga);

    lungb = clean(b, lungb);

    if(lunga > lungb) {
            return 1;
    }
    if(lungb > lunga) {
            return -1;
    }
    i = lunga - 1;
    while( b[i] == a[i] && i >= 0) {
        i--;
    }
    if(i < 0) {
            return 0;
    }
    if(a[i] > b[i]) {
            return 1;
    }
    if(b[i] > a[i]) {
            return -1;
    }
    return 0;
}

int cp(char a[], char b[], int lunga)
{
    int i;

    lunga = clean(a, lunga);

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

    return lunga;
}

int shift(char a[], int lunga, int dur)
{
    int i;

    lunga = clean(a, lunga);

    for(i = lunga - 1; i >= 0; i--) {
            a[i + dur] = a[i];
    }
    for(i = 0; i < dur; i++) {
            a[i] = 0;
    }

    lunga = lunga + dur;

    return lunga;
}

int inmultire(char a[], int lunga, int scalar)
{
    int i, transport;

    lunga = clean(a, lunga);

    transport = 0;
    for(i = 0; i < lunga; i++) {
        a[i] = a[i] * scalar + transport;
        transport = a[i] / 10;
        a[i] = a[i] % 10;
    }
    if(transport > 0) {
            a[lunga] = transport;
            lunga = lunga + 1;
    }

    return lunga;
}

int adunare(char a[], int lunga, int scalar)
{
    int i, transport, xa;

    transport = scalar;

    lunga = clean(a, lunga);

    for(i = 0; i < lunga; i++) {
            xa = a[i] + transport;
            if(xa >= 10) {
                transport = xa / 10;
                xa = xa % 10;
            } else {
                transport = 0;
            }
            a[i] = xa;
    }
    if(transport >= 0) {
            i = lunga;
            while(transport > 0) {
                    a[i] = transport % 10;
                    i++;
                    transport = transport / 10;
            }
            lunga = i;
    }

    return lunga;
}

int scadere(char a[], char b[], int lunga, int lungb)
{
    int i, transport, xa;

    lunga = clean(a, lunga);
    lungb = clean(b, lungb);

    transport = 0;

    for(i = 0; i < lungb; i++) {

        xa = a[i] - b[i] - transport;

        if(xa < 0) {
                xa = xa + 10;
                transport = 1;
        } else {
            transport = 0;
        }
        a[i] = xa;
    }
    while(transport == 1) {
            xa = a[i] - transport;
            if(xa < 0) {
                    xa = xa + 10 + transport;
                    transport = 1;
            } else {
                transport = 0;
            }
            a[i] = xa;
    }

    lunga = clean(a, lunga);

    return lunga;
}

int find(char a[], char b[], int lunga, int lungb)
{
    int i, lungc;

    char c[MAXX];

    lunga = clean(a, lunga);

    lungc = cp(a , c, lunga);

    i = 10;

    do
    {
        i = i - 1;

        lunga = cp(c , a, lungc);

        lunga = shift(a, lunga, 1);

        lunga = adunare(a, lunga, i);

        lunga = inmultire(a, lunga, i);

    }
    while(cmp(a, b, lunga, lungb) == 1 && i >= 0);
    nrdec = lunga;


    return i;
}

void init()
{
    int i, aux;
    char c;

    i = 0;
    c = fgetc(in);

    do
    {
        v[i] = c - '0';
        i++;
        c = fgetc(in);
    }
    while(c != EOF);

    nrv = i - 1;

    for(i = 0; i < nrv / 2; i++) {
            aux = v[i];
            v[i] = v[nrv - i - 1];
            v[nrv - i - 1] = aux;
    }
}




int main ()
{
    int x, i, j;

    in = fopen("sqrt.in", "r");
    out = fopen("sqrt.out", "w");

    init();

    if(nrv % 2 == 0) {
            x = v[nrv - 1] * 10 + v[nrv - 2];
    } else {
            x = v[nrv - 1];
    }

    i = 10;
    while(i * i > x) {
            i = i - 1;
    }

    fprintf(out, "%d", i);

    dec[0] = i;
    nrdec = 1;

    predec[0] = i;
    nrpredec = 1;

  /*

    dec[0] = 8;
    dec[1] = 1;
    dec[2] = 3;

    nrdec = 3;

    dscz[0] = 9;
    dscz[1] = 2;
    dscz[2] = 2;

    nrdscz = 3;

    //printf("%d\n\n", cmp(dec, dscz, nrdec, nrdscz));

    //x = find(dec, dscz, nrdec, nrdscz);

    nrdec = scadere(dec, dscz, nrdec, nrdscz);

    for(j = nrdec - 1; j >= 0; j--) {
            printf("%d ", dec[j]);
    }
    //printf("\n%d\n", x);
//*/
//*
    nrdec = adunare(dec, nrdec, i);

    x = x - (i * i);
    if(x > 10) {
            dscz[0] = x % 10;
            dscz[1] = x / 10;
            nrdscz = 2;
    } else {
        dscz[0] = x;
        nrdscz = 1;
    }
    if(nrv % 2 == 0) {
            i = 2;
    } else {
        i = 1;
    }
    i = nrv - i - 1;
    //printf("%d\n", i);
    for(i = i; i > 0; i = i - 2) {

            nrdscz = shift(dscz, nrdscz, 2);
            dscz[1] = v[i];
            dscz[0] = v[i - 1];

            nrdscz = cp(dscz, dscz, nrdscz);
/*
            for(j = nrdscz - 1; j >= 0; j--) {
                printf("%d", dscz[j]);
            }
            printf(" = dscz\n");
            printf("nrdscz = %d\n", nrdscz);
//*/
            nrpredec = cp(dec, predec, nrdec);

            x = find(dec, dscz, nrdec, nrdscz);
            //nrdec = nrdec + 1;
            //nrdec = cp(dec, dec, nrdec);
/*
            printf("x = %d\n", x);
            for(j = nrdec - 1; j >= 0; j--) {
                //printf(" dec[%d] = %d\n", j, dec[j]);
                printf("%d", dec[j]);
            }
            printf(" = dec\n");
            printf("nrdec = %d\n", nrdec);

//*/
            nrdscz = scadere(dscz, dec, nrdscz, nrdec);

/*
            for(j = nrdscz - 1; j >= 0; j--) {
                printf("%d", dscz[j]);
            }
            printf(" = dscz\n");
            printf("nrdscz = %d\n\n", nrdscz);
//*/
            fprintf(out, "%d", x);

            nrdec = cp(predec, dec, nrpredec);

            nrdec = shift(dec, nrdec, 1);

            nrdec = adunare(dec, nrdec, 2 * x);

            //nrdscz = cp(dscz, dscz, nrdscz);

    }

//*/


    fclose(in);
    fclose(out);

    return 0;
}