Advertisement
Guest User

Untitled

a guest
May 22nd, 2015
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <set>
  10. #include <map>
  11. #include <ctime>
  12. #include <cassert>
  13. using namespace std;
  14.  
  15. #ifdef LOCAL
  16.     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  17. #else
  18.     #define eprintf(...) 42
  19. #endif
  20.  
  21. typedef long long ll;
  22. const int BASE = (int)1e9;
  23. const int SZ = 16000 * 2;
  24.  
  25. /*
  26. const int M = (int)4e8;
  27. char buf[M];
  28. int mpos = 0;
  29.  
  30. void* operator new (size_t n)
  31. {
  32.     mpos += n;
  33.     assert(mpos < M);
  34.     return buf + mpos - n;
  35. }
  36.  
  37. void operator delete (void *) {}
  38. */
  39.  
  40. struct BigInt
  41. {
  42.     int a[SZ];
  43.     int sz;
  44.     BigInt () : a() {}
  45.     BigInt (int x)
  46.     {
  47.         sz = 0;
  48.         if (x == 0)
  49.             a[sz++] = 0;
  50.         while (x > 0)
  51.         {
  52.             a[sz++] = x % BASE;
  53.             x /= BASE;
  54.         }
  55.     }
  56.     BigInt operator + (const BigInt &b)
  57.     {
  58.         BigInt res = BigInt();
  59.         int border = max(sz, b.sz);
  60.         int z = 0;
  61.         for (int i = 0; i < border || z; i++)
  62.         {
  63.             int value = (i < sz ? a[i] : 0) + (i < b.sz ? b.a[i] : 0) + z;
  64.             res.a[res.sz++] = value % BASE;
  65.             z = value / BASE;
  66.         }
  67.         return res;
  68.     }
  69.     BigInt operator - (const BigInt &b)
  70.     {
  71.         BigInt res = *this;
  72.         int z = 0;
  73.         for (int i = 0; i < sz; i++)
  74.         {
  75.             res.a[i] -= (i < b.sz ? b.a[i] : 0) + z;
  76.             if (res.a[i] < 0)
  77.             {
  78.                 res.a[i] += BASE;
  79.                 z = 1;
  80.             }
  81.             else
  82.                 z = 0;
  83.         }
  84.         while (res.sz > 1 && res.a[res.sz - 1] == 0)
  85.             res.sz--;
  86.         return res;
  87.     }
  88.     BigInt operator * (int b)
  89.     {
  90.         BigInt res = BigInt();
  91.         int z = 0;
  92.         for (int i = 0; i < sz || z; i++)
  93.         {
  94.             ll value = (i < sz ? a[i] : 0) * (ll)b + z;
  95.             res.a[res.sz++] = value % BASE;
  96.             z = value / BASE;
  97.         }
  98.         return res;
  99.     }
  100.     void shift(int x)
  101.     {
  102.         if (sz == 1 && a[0] == 0) return;
  103.         while (x > 0)
  104.         {
  105.             sz++;
  106.             for (int i = sz - 1; i > 0; i--)
  107.                 a[i] = a[i - 1];
  108.             a[0] = 0;
  109.             x--;
  110.         }
  111.     }
  112.     bool operator < (const BigInt &b) const
  113.     {
  114.         if (sz != b.sz)
  115.             return sz < b.sz;
  116.         for (int i = (int)sz - 1; i >= 0; i--)
  117.             if (a[i] != b.a[i])
  118.                 return a[i] < b.a[i];
  119.         return false;
  120.     }
  121.     bool operator == (const BigInt &b) const
  122.     {
  123.         if (sz != b.sz)
  124.             return false;
  125.         for (int i = 0; i < (int)sz; i++)
  126.             if (a[i] != b.a[i])
  127.                 return false;
  128.         return true;
  129.     }
  130.     bool operator <= (const BigInt &b) const
  131.     {
  132.         if (sz != b.sz)
  133.             return sz < b.sz;
  134.         for (int i = (int)sz - 1; i >= 0; i--)
  135.             if (a[i] != b.a[i])
  136.                 return a[i] < b.a[i];
  137.         return true;
  138.     }
  139.     void print()
  140.     {
  141.         printf("%d", a[sz - 1]);
  142.         for (int i = sz - 2; i >= 0; i--)
  143.             printf("%09d", a[i]);
  144.         puts("");
  145.     }
  146. };
  147.  
  148. bool check(BigInt &delta, BigInt &value, int x)
  149. {
  150.     BigInt A = BigInt(x);
  151.     BigInt cur = value * 2 * x + A * x;
  152.     eprintf("Check %d\n", x);
  153.     return cur <= delta;
  154. }
  155.  
  156. void printDigits(int d, int k)
  157. {
  158.     char value[12];
  159.     sprintf(value, "%09d", d);
  160.     for (int i = 0; i < min(k, 9); i++)
  161.         printf("%c", value[i]);
  162. }
  163.  
  164. int main()
  165. {
  166.     freopen ("input.txt", "r", stdin);
  167.     freopen ("output.txt", "w", stdout);
  168.     int n, k;
  169.     scanf("%d%d", &n, &k);
  170.     BigInt delta;
  171.     BigInt value;
  172.     for (int x = n; x >= 0; x--)
  173.     {
  174.         if (x * x <= n)
  175.         {
  176.             printf("%d.", x);
  177.             delta = BigInt(n) - BigInt(x) * x;
  178.             value = BigInt(x);
  179.             break;
  180.         }
  181.     }
  182.     while (k > 0)
  183.     {
  184.         delta.shift(2);
  185.         value.shift(1);
  186.         int l = 0, r = BASE;
  187.         while (r - l > 1)
  188.         {
  189.             int m = (l + r) / 2;
  190.             if (check(delta, value, m))
  191.                 l = m;
  192.             else
  193.                 r = m;
  194.         }
  195.         eprintf("k = %d, value size = %d, delta size = %d\n", k, value.sz, delta.sz);
  196.         return 0;
  197.         printDigits(l, k);
  198.         k -= 9;
  199.         BigInt A = BigInt(l);
  200.         delta = delta - (value * 2 * l + A * l);
  201.         value = value + A;
  202.     }
  203.  
  204.     return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement