eolymp
Задачи

Весы

Весы

prb7110 Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из 7 гирь весом 1 г, 3 г, 9 г, 27 г, 81 г, 243 г и 729 г можно измерить вес любого предмета с целым весом от 1 до 1093 г единственным способом. Например, для измерения предмета весом 4 г необходимо на одну чашу положить гири в 1 и 3 г, а на другую сам предмет, а, скажем, для предмета весом 68 г на чашку с ним добавляются гири в 1, 3 и 9 г, а на другую - гиря в 81 г.

Определите, сколько гирь из данного набора необходимо использовать для взвешивания предмета заданного веса.

Входные данные

Одно натуральное число x (1x1000) - вес предмета.

Выходные данные

Вывести количество гирь, необходимых для взвешивания данного предмета.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
Выходные данные #1
2
Входные данные #2
68
Выходные данные #2
4
Автор Александр Буланый
Источник 2013 XXVII Всеукраинская олимпиада по информатике, II этап, Днепропетровск, Декабрь 28, Задача D