THRPWRS - III Powers

no tags 

Consider the set of all non-negative integer powers of 3.

S = { 1, 3, 9, 27, 81, ... }

Consider the sequence of all subsets of S ordered by the value of the sum of their elements. The question is simple: find the set at the n-th position in the sequence and print it in increasing order of its elements.

Each line of input contains a number n, which is a positive integer with no more than 19 digits. The last line of input contains 0 and it should not be processed.

For each line of input, output a single line displaying the n-th set as described above, in the format used in the sample output.

Example

Input:
1
7
14
783
1125900981634049
0

Output:
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }

hide comments
:.Mohib.:: 2015-06-21 15:37:42

Nice One..... Enjoyed it.... :)

[Lakshman]: 2014-12-31 16:56:15

@Vamsi Krishna Avula Actually this problem was in tutorial section , it was moved to Classical some time ago by EB mambers. Less people are interested in solving Tutorial problems.

Vamsi Krishna Avula: 2014-12-31 16:27:41

really easy problem! wonder why there are only 9 solutions..

Mitch Schwartz: 2014-11-22 21:15:02

There is a trickier problem on SHORTEN that is a little similar: WEIGHING.

I leaned toward tutorial at the time the problem was published. See screenshots one and two for background. (For reasons we can only guess at, the problem was originally published with a remotely hosted image that was essentially unrelated to the problem and that covered up a large portion of the problem text.)

As I wrote, I don't really enjoy classical/tutorial debates. So, moved to classical. :)

For anyone interested, my Python golf results are 87 bytes relying on a sort of input weakness, and 94 for general solution.

Last edit: 2014-11-22 23:25:21
wisfaq: 2014-11-21 22:43:34

I agree that a larger input file or more input files would have been better to compare algoritms.
Perhaps we could design something similar (not with powers of 3 but something else: e.g. Lucas numbers)
Or a challenge version on code size.
As it is now in tutorial it seems that nobody is interested.

--ans(Francky)--> Take a look at VUDBOL7. Maybe you'll find an interest and similar piece of code... (???)
And this one too.

Last edit: 2014-11-21 22:56:27
Francky: 2014-11-21 21:09:02

I did perhaps something comparable in classical, but don't remember it. I'm OK to put it classical. I think this task belongs to Mitch if he wants to, as first EB solver here.
--edit--> But input file could have been made bigger...

Last edit: 2014-11-21 22:27:31
wisfaq: 2014-11-21 14:33:55

Nice problem. Not difficult.
I don't know if something comparable is in classical, but if not doesn't it deserve to be there?


Added by:Vamos
Date:2013-06-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64