ivnikkk

Untitled

Jul 18th, 2022
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(d) d.begin(), d.end()
  6. #define int long long
  7. int find_first_bit(int k) {
  8.     int bit = 0;
  9.     for (int i = 31; i >= 0; i--) {
  10.         if ((k >> i) & 1) {
  11.             bit = i;
  12.             break;
  13.         }
  14.     }
  15.     return bit;
  16. }
  17. signed main() {
  18. #ifdef _DEBUG
  19.     freopen("input.txt", "r", stdin);
  20.     freopen("output.txt", "w", stdout);
  21. #endif
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24.     cout.tie(nullptr);
  25.     vector<vector<int>> c(32, vector<int>(32));
  26.     for (int i = 0; i < 32; i++) {
  27.         c[i][0] = 1;
  28.     }
  29.     for (int n = 1; n < 32; n++) {
  30.         for (int k = 1; k <= n; k++) {
  31.             c[n][k] = c[n - 1][k - 1] + c[n - 1][k];
  32.         }
  33.     }
  34.     int k; cin >> k;
  35.     int fst_bt = find_first_bit(k);
  36.     int ans = 0;
  37.     for (int len = 1; len < fst_bt; len++) {
  38.         int len_mn = (len + 1) / 2 + (len + 1) % 2;
  39.  
  40.         for (int i = len_mn; i <= len; i++) {
  41.             ans += c[len][i];
  42.         }
  43.     }
  44.     int len_mn = (fst_bt + 1) / 2 + (fst_bt + 1) % 2;
  45.     for (int i = fst_bt - 1; i >= 0; i--) {
  46.         int bit = (k >> i) & 1;
  47.         if (bit == 0) {
  48.             len_mn--;
  49.             continue;
  50.         }
  51.         else {
  52.             int need = max(0ll, len_mn - 1);
  53.             if (need > i) {
  54.                 break;
  55.             }
  56.             for (int j = need; j <= i; j++) {
  57.                 ans += c[i][j];
  58.             }
  59.         }
  60.     }
  61.     int to = len_mn <= 0;
  62.     cout << "There are " << ans + to << " round numbers less than or equal to " << k << ".";
  63. }
Advertisement
Add Comment
Please, Sign In to add comment