Cod sursă (job #503352)

#include <fstream>
#include <cstring>

using namespace std;

ifstream cin ("sqrt.in");
ofstream cout ("sqrt.out");

struct Number {
  short nr, a[3005];
  Number() {
    memset(a, 0, sizeof(a));
    nr = 0;
  }
  Number(int number) {
    memset(a, 0, sizeof(a));
    nr = 0;
    while(number)
      a[++nr] = number % 10, number /= 10;
  }
  bool operator == (const Number &other) const {
    if(nr != other.nr)
      return false;
    for(int i = 1; i <= nr; i++) {
      if(a[i] != other.a[i])
        return false;
    }
    return true;
  }
  bool operator <= (const Number &other) const {
    if(nr < other.nr)
      return true;
    if(nr > other.nr)
      return false;
    for(int i = nr; i >= 1; i--) {
      if(a[i] < other.a[i])
        return true;
      if(a[i] > other.a[i])
        return false;
    }
    return true;
  }
  Number operator + (const Number &other) const {
    short t = 0, i;
    Number ans = Number();
    for(i = 1; i <= nr || i <= other.nr || t; i++, t /= 10)
      ans.a[i] = (t += a[i] + other.a[i]) % 10;
    ans.nr = i - 1;
    return ans;
  }
  Number operator * (const Number &other) const {
    Number ans = Number();
    for(int i = 1; i <= nr; i++) {
      short t, j;
      for(t = 0, j = 1; j <= other.nr || t; j++, t /= 10)
        ans.a[i + j - 1] = (t += ans.a[i + j - 1] + a[i] * other.a[j]) % 10;
      if(i + j - 2 > ans.nr) {
        ans.nr = i + j - 2;
      }
    }
    return ans;
  }
  Number operator / (int number) const {
    Number ans = Number();
    short t = 0, i;
    ans.nr = nr;
    for(i = nr; i >= 1; i--, t %= number)
      ans.a[i] = (t = t * 10 + a[i]) / number;
    while(!ans.a[ans.nr] && ans.nr > 1)
      ans.nr--;
    return ans;
  }
  Number operator - (const Number &other) const {
    short i, t = 0;
    Number tmp = Number();
    for(i = 1; i <= nr; i++) {
      tmp.a[i] = a[i] - t - (i <= other.nr ? other.a[i] : 0);
      if(tmp.a[i] < 0)
        t = 1, tmp.a[i] += 10;
      else
        t = 0;
    }
    tmp.nr = i;
    for(; tmp.a[tmp.nr] == 0 && tmp.nr > 1; tmp.nr--);
    return tmp;
  }
};

int n;

string s;
Number num;

int main() {
  cin >> s;
  for(int i = s.size() - 1; i >= 0; i--)
    num.a[++num.nr] = s[i] - '0';
  Number l = (Number)1, r, mid;
  r.nr = num.nr / 2 + 2, r.a[num.nr / 2 + 2] = 1;
  while(l <= r) {
    mid = (l + r) / 2;
    if(mid * mid <= num)
      l = mid + (Number)1;
    else
      r = mid - (Number)1;
  }
  num = r;
  for(int i = num.nr; i >= 1; i--)
    cout << num.a[i];
  return 0;
}