Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <set>
- #include <map>
- #include <ctime>
- #include <cassert>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...) 42
- #endif
- typedef long long ll;
- const int BASE = (int)1e9;
- const int SZ = 16000 * 2;
- /*
- const int M = (int)4e8;
- char buf[M];
- int mpos = 0;
- void* operator new (size_t n)
- {
- mpos += n;
- assert(mpos < M);
- return buf + mpos - n;
- }
- void operator delete (void *) {}
- */
- struct BigInt
- {
- int a[SZ];
- int sz;
- BigInt () : a() {}
- BigInt (int x)
- {
- sz = 0;
- if (x == 0)
- a[sz++] = 0;
- while (x > 0)
- {
- a[sz++] = x % BASE;
- x /= BASE;
- }
- }
- BigInt operator + (const BigInt &b)
- {
- BigInt res = BigInt();
- int border = max(sz, b.sz);
- int z = 0;
- for (int i = 0; i < border || z; i++)
- {
- int value = (i < sz ? a[i] : 0) + (i < b.sz ? b.a[i] : 0) + z;
- res.a[res.sz++] = value % BASE;
- z = value / BASE;
- }
- return res;
- }
- BigInt operator - (const BigInt &b)
- {
- BigInt res = *this;
- int z = 0;
- for (int i = 0; i < sz; i++)
- {
- res.a[i] -= (i < b.sz ? b.a[i] : 0) + z;
- if (res.a[i] < 0)
- {
- res.a[i] += BASE;
- z = 1;
- }
- else
- z = 0;
- }
- while (res.sz > 1 && res.a[res.sz - 1] == 0)
- res.sz--;
- return res;
- }
- BigInt operator * (int b)
- {
- BigInt res = BigInt();
- int z = 0;
- for (int i = 0; i < sz || z; i++)
- {
- ll value = (i < sz ? a[i] : 0) * (ll)b + z;
- res.a[res.sz++] = value % BASE;
- z = value / BASE;
- }
- return res;
- }
- void shift(int x)
- {
- if (sz == 1 && a[0] == 0) return;
- while (x > 0)
- {
- sz++;
- for (int i = sz - 1; i > 0; i--)
- a[i] = a[i - 1];
- a[0] = 0;
- x--;
- }
- }
- bool operator < (const BigInt &b) const
- {
- if (sz != b.sz)
- return sz < b.sz;
- for (int i = (int)sz - 1; i >= 0; i--)
- if (a[i] != b.a[i])
- return a[i] < b.a[i];
- return false;
- }
- bool operator == (const BigInt &b) const
- {
- if (sz != b.sz)
- return false;
- for (int i = 0; i < (int)sz; i++)
- if (a[i] != b.a[i])
- return false;
- return true;
- }
- bool operator <= (const BigInt &b) const
- {
- if (sz != b.sz)
- return sz < b.sz;
- for (int i = (int)sz - 1; i >= 0; i--)
- if (a[i] != b.a[i])
- return a[i] < b.a[i];
- return true;
- }
- void print()
- {
- printf("%d", a[sz - 1]);
- for (int i = sz - 2; i >= 0; i--)
- printf("%09d", a[i]);
- puts("");
- }
- };
- bool check(BigInt &delta, BigInt &value, int x)
- {
- BigInt A = BigInt(x);
- BigInt cur = value * 2 * x + A * x;
- eprintf("Check %d\n", x);
- return cur <= delta;
- }
- void printDigits(int d, int k)
- {
- char value[12];
- sprintf(value, "%09d", d);
- for (int i = 0; i < min(k, 9); i++)
- printf("%c", value[i]);
- }
- int main()
- {
- freopen ("input.txt", "r", stdin);
- freopen ("output.txt", "w", stdout);
- int n, k;
- scanf("%d%d", &n, &k);
- BigInt delta;
- BigInt value;
- for (int x = n; x >= 0; x--)
- {
- if (x * x <= n)
- {
- printf("%d.", x);
- delta = BigInt(n) - BigInt(x) * x;
- value = BigInt(x);
- break;
- }
- }
- while (k > 0)
- {
- delta.shift(2);
- value.shift(1);
- int l = 0, r = BASE;
- while (r - l > 1)
- {
- int m = (l + r) / 2;
- if (check(delta, value, m))
- l = m;
- else
- r = m;
- }
- eprintf("k = %d, value size = %d, delta size = %d\n", k, value.sz, delta.sz);
- return 0;
- printDigits(l, k);
- k -= 9;
- BigInt A = BigInt(l);
- delta = delta - (value * 2 * l + A * l);
- value = value + A;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement