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
#include <stdio.h>
#define Max 130000
#define SumMax 1101195

int bits[Max+1];
int prefSum[Max+1];
int map[SumMax+1]; //given index (idx1) stores index (idx2) of prefSum whose value is equal or greater than idx1
int result[Max+1];

int num_to_bits[16] = { 0, 1, 1, 2, 1, 2, 2, 3,
						1, 2, 2, 3, 2, 3, 3, 4 };

int countSetBitsRec(int num)
{
	int nibble = 0;
	if (0 == num)
		return num_to_bits[0];
	nibble = num & 0xf;
	return num_to_bits[nibble] + countSetBitsRec(num >> 4);
}

void init() {
	bits[0] = 0;
	prefSum[0] = 0;
	for(int i=1; i <= Max; i++){
		bits[i] = countSetBitsRec(i);
		prefSum[i] = prefSum[i-1] + bits[i];
	}
	for(int idx1=1, idx2=1, value=prefSum[idx2]; idx1 <= SumMax; idx1++){
		if(idx1 > value) {
			idx2++;
			value = prefSum[idx2];
		}
		map[idx1] = idx2;
	}
	// for(int i=1; i <= 16; i++){
	// 	printf("%d: %d %d %d\n", i, bits[i], prefSum[i], map[i]);
	// }
}

int main() {
	init();
	int n=0; scanf("%d", &n);
	int idx = 0;
	while(n > 0){
		int number = map[n];
		n -= bits[number];
		result[idx] = number;
		idx++;
	}
	printf("%d\n", idx);
	for(int i=0; i < idx; i++){
		printf("%d ", result[i]);
	}
	printf("\n");
	return 0;
}