Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(d) d.begin(), d.end()
- #define int long long
- int find_first_bit(int k) {
- int bit = 0;
- for (int i = 31; i >= 0; i--) {
- if ((k >> i) & 1) {
- bit = i;
- break;
- }
- }
- return bit;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- vector<vector<int>> c(32, vector<int>(32));
- for (int i = 0; i < 32; i++) {
- c[i][0] = 1;
- }
- for (int n = 1; n < 32; n++) {
- for (int k = 1; k <= n; k++) {
- c[n][k] = c[n - 1][k - 1] + c[n - 1][k];
- }
- }
- int k; cin >> k;
- int fst_bt = find_first_bit(k);
- int ans = 0;
- for (int len = 1; len < fst_bt; len++) {
- int len_mn = (len + 1) / 2 + (len + 1) % 2;
- for (int i = len_mn; i <= len; i++) {
- ans += c[len][i];
- }
- }
- int len_mn = (fst_bt + 1) / 2 + (fst_bt + 1) % 2;
- for (int i = fst_bt - 1; i >= 0; i--) {
- int bit = (k >> i) & 1;
- if (bit == 0) {
- len_mn--;
- continue;
- }
- else {
- int need = max(0ll, len_mn - 1);
- if (need > i) {
- break;
- }
- for (int j = need; j <= i; j++) {
- ans += c[i][j];
- }
- }
- }
- int to = len_mn <= 0;
- cout << "There are " << ans + to << " round numbers less than or equal to " << k << ".";
- }
Advertisement
Add Comment
Please, Sign In to add comment