SPOJ.com - Problem THRPWRS

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 }

Submit solution!

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?

Submit solution!

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