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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// muz.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

struct note
{
	note()
	{
		value = 0;
		used = false;
		bits = 0;
	}
	note(int value)
	{
		setValue(value);
	}

	void setValue(int value)
	{
		this->value = value;
		used = true;
		bits = calcBits(value);
	}

	int calcBits(int v)
	{
		int tmpBits = 0;
		while (v)
		{
			if (v & 1) tmpBits++;
			v >>= 1;
		}
		return tmpBits;
	}

	bool isUsed() { return used; }
	void makeNotUsed() { used = false; }
	int getBits() { return used ? bits : 0; }

private:
	int value;
	bool used;
	int bits;
};
int main()
{
	int n;
	scanf("%d", &n);

	int i = 0;
	//int ones = 0;
	note* sounds = new note[130'000];

	//calc sounds
	while (n > 0)
	{
		i++;
		sounds[i] = note(i);
		n -= sounds[i].getBits();

		//ones += sounds[i].getBits();
		//if (sounds[i].getBits() > ones) printf("for %d: %d bits and only %d ones before \n", i, sounds[i].getBits(), ones);
		//printf("%d %d   ", i, sound.getBits());
	}

	//regresion
	if (n < 0) n = -n;

	int maxI = i;
	int length = i;
	while (n > 0)
	{
		i--;
		if (sounds[i].getBits() <= n)
		{
			n -= sounds[i].getBits();
			sounds[i].makeNotUsed();
			length--;
		}
	}

	printf("%d\n", length);

	for (i = maxI; i >= 1; i--)
	{
		if (sounds[i].isUsed()) printf("%d ", i);
	}

	return 0;
}