eolymp
bolt
Try our new interface for solving problems
Məsələlər

Старовинна задача

Старовинна задача

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Готуючись до чергової олімпіади з програмування, Степан натрапив на одну старовинну задачу, яка його зразу ж зацікавила. У задачі йшлося про те, що у країні, яка називалась Триманія, номінали усіх паперових грошей (триманських фунтів) дорівнювали ступеням трійки, тобто 1, 3, 9, 27 і так далі. Необхідно було визначити, яку мінімальну кількість купюр і яких саме потрібно мати покупцю та продавцю, щоб купити товар вартістю N триманських фунтів та отримати здачу, причому номінали купюр, якими розплачуються та отримують здачу, не повинні повторюватися.

Giriş verilənləri

Вхідний файл містить одне число – N (вартість товару у фунтах, 0 ≤ N ≤10^18).

Çıxış verilənləri

Один рядок містить номінали купюр у зростаючому порядку через пробіл, які потрібні для купівлі товару покупцю та продавцю, або –1, якщо купити товар за означених умов неможливо.

Nümunə

Giriş verilənləri #1
11
Çıxış verilənləri #1
1 3 9 
Mənbə ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року