ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Tips

Time limit: 1.0 second
Memory limit: 64 MB
The favorite resting place of the Ural programmers is Threenland island. There is only one tribulation: dollars and euro don’t go about here. So the tourists are to exchange their money into threets (the currency of Threenland). There go about 1 threet, 3 threets, 9 threets, 27 threets, …, 3k threets, … Once programmer Vasechkin, after the N-threets bill was given to him found out, that he’d got one paper of each denomination. Waiters in Threenland have a custom to keep the change. Waiters like to get the tip that can be presented by a set of papers in which paper of each denomination appears not more than once. Otherwise their feelings are hurt. They have a peeve on a client if they don’t get tips at all. Help please Vasechkin to pay for the dinner and not to hurt the waiter.


consists of an integer N. 1 ≤ N ≤ 107.


Output two integers separated with a space – that is the sum that Vasechkin is to pay and an amount of tips. If there are several solutions choose any of them. If there is no solution output 0. Remember that Ural programmers are not rich, so Vasechkin can’t pay more than 4294967291 threets.


9 4
Problem Author: Alexander Ipatov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003
To submit the solution for this problem go to the Problem set: 1261. Tips