学步园

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
using namespace std;
#define maxlen 4000
void mul(int k, int a[], int *lena)
{
    for(int i = 0; i < *lena; i++)
        a[i] *= k;
    for(int i = 0; i < *lena; i++)
    {
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    }
    while(a[*lena])
    {
        a[*lena + 1] += a[*lena] / 10;
        a[*lena] %= 10;
        (*lena)++;
    }
    return;
}
bool judge(int a[], int lena, int b[], int lenb)
{
    if(lena < lenb)
        return 0;
    for(int i = lena - 1; i >= 0; i--)
        if(a[i] > b[i])
            return 1;
        else if(a[i] < b[i])
            return 0;
    return 0;
}
bool func(int m, int nr[], int lennr, int R[], int lenR)
{
    mul(20 * m, nr, &lennr);
    nr[0] += m * m;
    lennr = max(lennr, 1);
    for(int i = 0; i < lennr; i++)
    {
        nr[i + 1] += nr[i] / 10;
        nr[i] %= 10;
    }
    while(nr[lennr])
    {
        nr[lennr + 1] += nr[lennr] / 10;
        nr[lennr] %= 10;
        lennr++;
    }
    return judge(nr, lennr, R, lenR);
}
void newR(int k, int r[], int lenr, int R[], int *lenR)
{
    mul(20 * k, r, &lenr);
    for(int i = 0; i < *lenR; i++)
    {
        R[i] -= r[i];
        if(!i)
            R[i] -= k * k;
        while(R[i] < 0)
        {
            R[i] += 10;
            R[i + 1]--;
        }
    }
    while(*lenR && !R[*lenR - 1])
        (*lenR)--;
    return;
}
int main()
{
    int N[maxlen], lenN, R[maxlen], lenR = 0, r[maxlen], lenr = 0;
    memset(N, 0, sizeof(N));
    memset(R, 0, sizeof(R));
    memset(r, 0, sizeof(r));
    string str;
    cin >> str;
    lenN = str.size();
    for(int i = lenN - 1; i >= 0; i--)
        N[i] = (char)str[lenN - 1 - i] - '0';
/*check the number
    for(int i = lenN - 1; i >= 0; i--)
        cout << N[i];
    cout << endl;
*/
    for(int i = lenN - 1; i >= 0; i--)
    {
        if(i & 1)
            continue;
        for(int j = lenR - 1; j >= 0; j--)
            R[j + 2] = R[j];
        R[1] = N[i + 1];
        R[0] = N[i];
        lenR += 2;
        while(lenR && !R[lenR - 1])
            lenR--;
        int k, nr[maxlen], lennr = lenr;
        for(k = 0; k < 10; k++)
        {
            memcpy(nr, r, sizeof(nr));
            if(func(k + 1, nr, lennr, R, lenR))
                break;
        }
        memcpy(nr, r, sizeof(nr));
        newR(k, nr, lennr, R, &lenR);
        for(int j = lenr - 1; j >= 0; j--)
            r[j + 1] = r[j];
        r[0] = k;
        lenr++;
    }
    for(int i = lenr - 1; i >= 0; i--)
        cout << r[i];
    cout << endl;
    return 0;
}