sgu101-121.rar_sgu_sgu101 pascal

#include <stdio.h> #include <memory.h> const int nmax = 1000, mo = 100000, pmax = nmax/4; int ans[pmax + 18], r; int ans0, s0, y0, len, da0; int shang[pmax + 18], da[pmax + 18]; int yu[pmax + 18], tmp[pmax + 18]; char str[nmax + 18]; int max(int a, int b) { return a > b ? a : b; } void cheng(int *a, int k, int &l) { for (int i = 1; i <= l; ++i) a[i] *= k; for (int i = 1; i <= l; ++i) if (a[i] > mo) { a[i + 1] += a[i] / mo; a[i] %= mo; if (i == l) ++l; } } void add(int *a, int k, int &l) { a[1] += k; for (int i = 1; i <= l; ++i) if (a[i] > mo) { a[i + 1] += a[i] / mo; a[i] %= mo; if (i == l) ++l; } else break; } bool big(int *a, int l, int k) { memcpy(tmp, a, (max(l, r) + 1) * sizeof(int)); add(tmp, k, l); cheng(tmp, k, l); r = l; if (l != y0) return l > y0; for (int i = l; i; --i) if (tmp[i] != yu[i]) return tmp[i] > yu[i]; return false; } void dec(int k) { memcpy(tmp, shang, (max(r, s0) + 1) * sizeof(int)); cheng(tmp, k, r); for (int i = 1; i <= r; ++i) { yu[i] -= tmp[i]; if (yu[i] < 0) { yu[i] += mo; --yu[i + 1]; } } while (!yu[y0] && y0 > 1) --y0; } int main() { freopen("input.txt", "r", stdin); freopen("111.out", "w", stdout); scanf("%s\n", str + 1); len = strlen(str + 1); s0 = y0 = da0 = 1; for (int i = len, tmp = 0, k = 1; i; --i, k *= 10) { if (k == mo) ans[++ans0] = tmp, tmp = str[i] - '0', k = 1; else tmp += (str[i] - '0') * k; if (i == 1) ans[++ans0] = tmp; } int now = mo / 10; if (len & 1) { int k = ans[ans0], wei = 1, i;now = 1; while (k >= 10) k /= 10, wei *= 10, now *= 10;now /= 10; ans[ans0] -= wei * k; for (i = 1; i * i <= k; ++i); i--; da[1] = i; printf("%d", i); yu[1] = k - i * i; len--; } else while (now > ans[ans0]) now /= 10; for (int i = len, l, r; i; i -= 2) { memcpy(shang, da, (max(s0, da0) + 1) * sizeof(int)); s0 = da0; if (!now) ans0--, now = mo / 10; if (now < 10) { l = ans[ans0] % 10 * 10; l += ans[--ans0] / (mo / 10); now = mo / 100; } else { l = (ans[ans0] / now % 10)* 10 + ans[ans0] / (now / 10) % 10; now /= 100; } cheng(yu, 100, y0); add(yu, l, y0); cheng(shang, 20, s0); l = 0, r = 9; for (int mid = (l + r + 1) >> 1; l < r; mid = (l + r + 1) >> 1) { if (big(shang, s0, mid)) r = mid - 1; else l = mid; } printf("%d", l); add(shang, l, s0); cheng(da, 10, da0); add(da, l, da0); dec(l); } return 0; }