У ювелира есть весы с двумя чашками, он может определять равны ли массы грузов, лежащих на двух чашках, а если не равны – то на какой чашке лежит более лёгкий груз.
Масса ювелирного изделия, которую нужно определить ювелиру, является целым числом от 1 до N. Ювелир должен запасти набор гирек (их массы также должны быть целыми числами), используя которые ювелир может определить любую возможную массу от 1 до N. Для определения массы ювелир может производить любое число взвешиваний, может использовать все гирьки или только некоторые из них, может класть гирьки на разные чашки весов.
Определите набор гирек, содержащий минимальное возможное число гирек, используя который можно определить любую возможную целочисленную массу от 1 до N.
Программа получает на вход натуральное число N (2 ≤ N ≤ 10
8) – максимально допустимую массу ювелирного изделия.
Программа должна вывести несколько натуральных чисел, не превосходящих 10
9, – массы гирек в минимальном требуемом для решения задачи наборе (допускается использовать гирьки массой, больше, чем N, если их масса не превосходит 10
9).
Если задача имеет множество решений, необходимо вывести любое из них.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3 |
2 |
Пусть x – изделие, массу которого необходимо определить. Нужно на одну чашу весов положить x, а на другую чашу весов – гирьку в 2. Если x будет легче, то x = 1, при равенстве – x = 2, если x тяжелее, то x = 3. |
| 2 |
5 |
3 4 |
Покажем, как при помощи гирек в 3 и 4 определить все массы от 1 до 5. Массы 3 и 4 можно определить при помощи равенств x = 3 и x = 4. Массу 1 можно определить при помощи равенства x + 3 = 4 (на одну чашу кладется изделие и гирька массой 3, на другую чашу – гирька массой 4). Массу 2 можно определить, например, по условию x < 3 (на одну чашу весов кладется изделие, на другую – гирька массой 3), а также проверив при помощи ранее описанного алгоритма, что x ≠ 1 . Массу 5 можно определить при помощи взвешивания x > 4. |