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
#include <iostream>

using namespace std;

int zapalone_bity(int liczba)
{
    int liczba_zapalonych_bitow=0;
    int waga;

    for(liczba_zapalonych_bitow; liczba>0; liczba_zapalonych_bitow++)
    {
        waga=1;
        while(waga*2<=liczba) waga*=2;
        liczba-=waga;
    }

    return liczba_zapalonych_bitow;
}

void najmniejsze_zakonczenie(int liczba, int *ostatnia_liczba_rozpoczynajaca_sie, int *liczba_zapalonych_bitow, int &dlugosc_zakonczenia, int *zakonczenie, int poczatkowy_bit)
{
    dlugosc_zakonczenia++;

    if(liczba==1)
        zakonczenie[dlugosc_zakonczenia-1] = 1;
    else
    {
        if(ostatnia_liczba_rozpoczynajaca_sie[poczatkowy_bit-2]>=liczba) poczatkowy_bit--;

        zakonczenie[dlugosc_zakonczenia-1] = poczatkowy_bit;

        najmniejsze_zakonczenie(liczba-liczba_zapalonych_bitow[poczatkowy_bit-1], ostatnia_liczba_rozpoczynajaca_sie, liczba_zapalonych_bitow, dlugosc_zakonczenia, zakonczenie, poczatkowy_bit-1);
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int suma_zapalonych_bitow;
    cin>>suma_zapalonych_bitow;

    int *liczba_zapalonych_bitow = new int [suma_zapalonych_bitow];
    int *ostatnia_liczba_rozpoczynajaca_sie = new int [suma_zapalonych_bitow];

    for(int i=0; i<suma_zapalonych_bitow; i++)
        liczba_zapalonych_bitow[i] = zapalone_bity(i+1);

    ostatnia_liczba_rozpoczynajaca_sie[0] = 1;
    for(int i=1; i<suma_zapalonych_bitow; i++)
        ostatnia_liczba_rozpoczynajaca_sie[i] = ostatnia_liczba_rozpoczynajaca_sie[i-1] + liczba_zapalonych_bitow[i];

    int *zakonczenie = new int [suma_zapalonych_bitow];
    int dlugosc_zakonczenia = 0;
    int poczatkowy_bit=1;

    while(ostatnia_liczba_rozpoczynajaca_sie[poczatkowy_bit-1]<suma_zapalonych_bitow) poczatkowy_bit++;

    najmniejsze_zakonczenie(suma_zapalonych_bitow, ostatnia_liczba_rozpoczynajaca_sie, liczba_zapalonych_bitow, dlugosc_zakonczenia, zakonczenie, poczatkowy_bit);

    cout<<dlugosc_zakonczenia<<'\n';
    for(int i=0; i<dlugosc_zakonczenia; i++)
        cout<<zakonczenie[i]<<" ";

    return 0;
}