tutorial/2019/F_elephant_2.cpp at master · sicamp/tutorial · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <queue>
#include <bitset>

using namespace std;

#define clr(a) memset(a, 0, sizeof(a))
#define pb push_back
#define forab(i, a, b) for(int i = int(a); i < int(b); ++i)
#define forba(i, b, a) for(int i = int(b) - 1; i >= int(a); --i)
#define forn(i, n) forab(i, 0, n)

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const int MAXN = 1e5;

int cnt = 0;
vector<int> res;
int n;

void rec(int pos, int num, int onesLeft) {
    if (pos == -1) {
        if (cnt < 1000) {
            res.push_back(num);
        }

        cnt++;
    }
    if (onesLeft < pos + 1) {
        rec(pos - 1, num, onesLeft);
    }
    if (onesLeft == 0) {
        return;
    }
    num += 1 << pos;
    if (num <= n) {
        rec(pos - 1, num, onesLeft - 1);
    }
}

int main() {
#ifdef LOCAL
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    //freopen("", "w", stderr);
#endif
    cin.sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> n >> k;
    assert(1 <= n && n <= 1e9);
    assert(0 <= k && k <= 10);
    rec(29, 0, k);
    cout << cnt << ' ';
    for (auto x : res) {
        cout << x << ' ';
    }
    cout << '\n';

    return 0;
}