Ancient Task#7674
While preparing for the upcoming programming olympiad, Stepan discovered an intriguing old problem. This problem involves a fictional country called Trimania, where all paper money denominations (in Trimanian pounds) are powers of three, such as , , , , and so forth. The challenge is to determine the minimum number of bills required, and exactly which denominations the buyer and seller should use, to purchase an item priced at Trimanian pounds and provide change. Importantly, the denominations used for both payment and change must not repeat.
The input consists of a single number, , representing the cost of the item in pounds, where 0 \le N \le 10^{18}.
The output should be a single line listing the denominations of the bills, in ascending order and separated by spaces, that the buyer and seller need to complete the purchase. If it is impossible to buy the item under the given conditions, output –1.
Example 1