SHARE
TWEET

Untitled

Lazit Jan 26th, 2020 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <set>
  6. #include <queue>
  7. #include <map>
  8. #include <string>
  9. #include <cmath>
  10. #include <functional>
  11. #include <algorithm>
  12. #include <utility>
  13. #include <stack>
  14. #include <unordered_map>
  15. #include <unordered_set>
  16. #include <iterator>
  17. #include <fstream>
  18. #include <iomanip>
  19. #include <time.h>
  20. #include <complex>
  21. //#pragma comment(linker, "/STACK:16777216")
  22.  
  23. using namespace std;
  24.  
  25. typedef long double C;
  26. typedef complex<C> P;
  27.  
  28. #define X real()
  29. #define Y imag()
  30. #define Size(X) (int)X.size()
  31. #define int long long
  32. #define ui unsigned int
  33. #define mp make_pair
  34. #define timer fghge
  35. #define y1 yjyjyju
  36. #define all(X) (X).begin(), (X).end()
  37. #define endl '\n'
  38.  
  39. int solve(int n) {
  40.     if (n == 1) {
  41.         return 0;
  42.     }
  43.  
  44.     int cnt = 1e18, st, sf;
  45.  
  46.     for (int m = 1; m < 60; m++) { 
  47.         vector<int> stack;
  48.         stack.push_back(1);
  49.         int p = 1;
  50.         for (int i = 0; i < m; i++) {
  51.             stack.push_back(p);
  52.             p *= 2;
  53.         }
  54.  
  55.         for (int j = 0; j <= stack.size(); j++) {
  56.             int cand = m;
  57.             int sum = 0;
  58.             for (int i = 0; i < j; i++)
  59.                 sum += stack[stack.size() - i - 1];
  60.             int num = n - sum;
  61.  
  62.             if (num < 0)
  63.                 break;
  64.  
  65.             if (num == 0) {
  66.                 if (cand + 1 < cnt) {
  67.                     cnt = cand + 1;
  68.                     st = m;
  69.                 }
  70.                 continue;
  71.             }
  72.  
  73.             vector<int> order;
  74.             while (num > 0) {
  75.                 order.push_back(num % 2);
  76.                 num /= 2;
  77.             }
  78.  
  79.             while (order.size() > m) {
  80.                 order[order.size() - 2] += order[order.size() - 1] * 2;
  81.                 order.pop_back();
  82.             }
  83.  
  84.             int l = 1, r = 1e18, ans;
  85.             while (l <= r) {
  86.                 bool flag = 1;
  87.                 int mid = (l + r) / 2;
  88.                 vector<int> cop = order;
  89.                 for (int i = cop.size() - 1; i >= 0; i--) {
  90.                     int delt = max(0LL, cop[i] - mid);
  91.                     if (i > 0)
  92.                         cop[i - 1] += 2 * delt;
  93.                     else if (delt > 0)
  94.                         flag = 0;
  95.                 }
  96.                 if (flag) {
  97.                     ans = mid;
  98.                     r = mid - 1;
  99.                 }
  100.                 else
  101.                     l = mid + 1;
  102.             }
  103.  
  104.             int ctr = 0;
  105.             for (int i = order.size() - 1; i >= 0; i--) {
  106.                 int delt = max(0LL, order[i] - ans);
  107.                 if (i > 0 && delt > 0) {
  108.                     order[i - 1] += 2 * delt;
  109.                     ctr++;
  110.                 }
  111.             }
  112.  
  113.             cand += ans;
  114.  
  115.             bool flag = 0;
  116.             int cntr = 0;
  117.             for (int i = 0; i < order.size(); i++) {
  118.                 if (order[i] >= 1)
  119.                     flag = 1;
  120.                 else if (flag == 1) {
  121.                     flag = 0;
  122.                     cntr++;
  123.                 }
  124.             }
  125.             if (flag == 1)
  126.                 cntr++;
  127.  
  128.             cand += cntr - 1;
  129.  
  130.             if (cand + 1 < cnt) {
  131.                 cnt = cand + 1;
  132.                 sf = j;
  133.                 st = m;
  134.             }
  135.         }
  136.     }
  137.  
  138.     /*vector<pair<int, int>> posl;
  139.  
  140.     int sum = (1LL << st);
  141.     int num = n - sum;
  142.  
  143.     for (int i = 0; i < st; i++)
  144.         posl.push_back({ 1, i + 1 });
  145.  
  146.     if (num > 0) {
  147.         vector<int> order;
  148.         while (num > 0) {
  149.             order.push_back(num % 2);
  150.             num /= 2;
  151.         }
  152.         while (order.size() > st) {
  153.             order[order.size() - 2] += order[order.size() - 1] * 2;
  154.             order.pop_back();
  155.         }
  156.  
  157.         int l = 1, r = 1e18, ans;
  158.         while (l <= r) {
  159.             bool flag = 1;
  160.             int mid = (l + r) / 2;
  161.             vector<int> cop = order;
  162.             for (int i = cop.size() - 1; i >= 0; i--) {
  163.                 int delt = max(0LL, cop[i] - mid);
  164.                 if (i > 0)
  165.                     cop[i - 1] += 2 * delt;
  166.                 else if (delt > 0)
  167.                     flag = 0;
  168.             }
  169.             if (flag) {
  170.                 ans = mid;
  171.                 r = mid - 1;
  172.             }
  173.             else
  174.                 l = mid + 1;
  175.         }
  176.  
  177.         for (int i = order.size() - 1; i >= 0; i--) {
  178.             int delt = max(0LL, order[i] - ans);
  179.             if (i > 0 && delt > 0) {
  180.                 order[i] -= delt;
  181.                 order[i - 1] += 2 * delt;
  182.             }
  183.         }
  184.  
  185.         for (int i = 1; i <= ans; i++) {
  186.             bool flag = 0; int ctr = 0, last;
  187.             for (int j = 0; j < order.size(); j++) {
  188.                 if (order[j] >= i) {
  189.                     if (flag == 0)
  190.                         last = j;
  191.                     flag = 1;
  192.                 }
  193.                 else if (flag == 1) {
  194.                     posl.push_back({ last + 2, j + 1 });
  195.                     flag = 0;
  196.                 }
  197.             }
  198.             if (flag == 1)
  199.                 posl.push_back({ last + 2, order.size() + 1 });
  200.         }
  201.     }
  202.  
  203.  
  204.     posl.push_back({ 1, posl.size() + 1 });
  205.     cout << posl.size() << endl;
  206.  
  207.     for (auto &i : posl)
  208.         cout << i.first << " " << i.second << endl;
  209.         */
  210.     return cnt;
  211. }
  212.  
  213. signed main() {
  214.     ios_base::sync_with_stdio(0);
  215.     cin.tie(0), cout.tie(0);
  216.     freopen("input.txt", "r", stdin);
  217.     //freopen("output.txt", "w", stdout);
  218.     for (int i = 2; i <= 100; i++) {
  219.         if (solve(i) != ceil(log2((double)i)) + 1) {
  220.             cout << i << " " << solve(i);
  221.             return 0;
  222.         }
  223.     }
  224.     return 0;
  225. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top