10669 - Three powers

bmouse001 · Post by **bmouse001** » Mon Jun 14, 2004 2:46 pm

I always got WA. Here's my test i/o.
Please tell me what's wrong...
input:
1
7
14
783
1125900981634049
999999999999999999
9999999999999999999
0
output:
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381059609, 282429536481, 847288609443, 2541865828329, 68630377364883, 617673396283947, 1853020188851841, 5559060566555523, 150094635296999121, 450283905890997363, 452555153018976267, 36472996377170786403, 109418989131512359209, 984770902183611232881, 2954312706550833698643, 26588814358957503287787, 19383245667680019896796723, 581497373040059690390169, 1744492119120179071170507, 52334763327360537213511521, 4710128697246244834921603689, 14130386091738734504764811067 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 10460353203, 31381059609, 94143178827, 282429536481, 7625597484987, 617673396283947, 16677181699666569, 12157665459056928801, 36472996377170786403, 2954312706550833698643, 79766443076872509863361, 239299329230617529590083, 717897987691852588770249, 581497373040059690390169, 1744492119120179071170507, 157004289982081611640534563, 14130386091738734504764811067, 1144561273430837494885949696427 }

Code: Select all

Dreamer#1 · Post by **Dreamer#1** » Mon Jun 14, 2004 4:05 pm

Find your mistakes from below:

Your output is not correct. Moreover, watch out for the proper use of spaces.

Your Output:

Code: Select all

{ } 
{ 3, 9 } 
{ 1, 9, 27 } 
{ 3, 9, 27, 6561, 19683 } 
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 } 
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381059609, 282429536481, 847288609443, 2541865828329, 68630377364883, 617673396283947, 1853020188851841, 5559060566555523, 150094635296999121, 450283905890997363, 452555153018976267, 36472996377170786403, 109418989131512359209, 984770902183611232881, 2954312706550833698643, 26588814358957503287787, 19383245667680019896796723, 581497373040059690390169, 1744492119120179071170507, 52334763327360537213511521, 4710128697246244834921603689, 14130386091738734504764811067 } 
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 10460353203, 31381059609, 94143178827, 282429536481, 7625597484987, 617673396283947, 16677181699666569, 12157665459056928801, 36472996377170786403, 2954312706550833698643, 79766443076872509863361, 239299329230617529590083, 717897987691852588770249, 581497373040059690390169, 1744492119120179071170507, 157004289982081611640534563, 14130386091738734504764811067, 1144561273430837494885949696427 }

Correct Output:

Code: Select all

{  }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381059609, 282429536481, 847288609443, 2541865828329, 68630377364883, 617673396283947, 1853020188851841, 5559060566555523, 150094635296999121, 450283905890997363, 4052555153018976267, 36472996377170786403, 109418989131512359209, 984770902183611232881, 2954312706550833698643, 26588814358957503287787, 19383245667680019896796723, 58149737003040059690390169, 174449211009120179071170507, 523347633027360537213511521, 4710128697246244834921603689, 14130386091738734504764811067 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363, 1350851717672992089, 4052555153018976267, 12157665459056928801, 36472996377170786403, 109418989131512359209, 328256967394537077627, 984770902183611232881, 2954312706550833698643, 8862938119652501095929, 26588814358957503287787, 79766443076872509863361, 239299329230617529590083, 717897987691852588770249, 2153693963075557766310747, 6461081889226673298932241, 19383245667680019896796723, 58149737003040059690390169, 174449211009120179071170507, 523347633027360537213511521, 1570042899082081611640534563, 4710128697246244834921603689, 14130386091738734504764811067, 42391158275216203514294433201, 127173474825648610542883299603, 381520424476945831628649898809 }

hope it helps.

regards

-Dreamer

sohel · Post by **sohel** » Mon Jun 14, 2004 4:49 pm

Strange!

My AC program gives a different output from that of Dreamer#1.

input
[c]
1
7
14
783
1125900981634049
999999999999999999
9999999999999999999
0
[/c]

My output ( AC )

[c]
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
{ 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381059609, 282429536481, 847288609443, 2541865828329, 68630377364883, 617673396283947, 1853020188851841, 5559060566555523, 150094635296999121, 450283905890997363, 4052555153018976267, 36472996377170786403, 109418989131512359209, 984770902183611232881, 2954312706550833698643, 26588814358957503287787, 19383245667680019896796723, 58149737003040059690390169, 174449211009120179071170507, 523347633027360537213511521, 4710128697246244834921603689, 14130386091738734504764811067 }
{ 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 10460353203, 31381059609, 94143178827, 282429536481, 7625597484987, 617673396283947, 16677181699666569, 12157665459056928801, 36472996377170786403, 2954312706550833698643, 79766443076872509863361, 239299329230617529590083, 717897987691852588770249, 58149737003040059690390169, 174449211009120179071170507, 1570042899082081611640534563, 14130386091738734504764811067, 1144561273430837494885949696427 }
[/c]

UFP2161 · Post by **UFP2161** » Mon Jun 14, 2004 5:16 pm

Dreamer #1's output is correct.. If you think about it, any odd input number should not have "1" as it's first output.. likewise, any even input number should..

bmouse001 · Post by **bmouse001** » Mon Jun 14, 2004 6:28 pm

Thanks you all, especially Dreamer, I finally got accepted.
I use 2 long long to hold the bit string, and I found a bug while displaying the second long long .

Thanks very much!!

Best Regards,
Liang

w k · Post by **w k** » Tue Jun 15, 2004 8:36 pm

I think that Dreamer's output for last input is not correct! For this input: 9999999999999999999>2^63+1, so the output should contain the bigest number = 3^63 = 1144561273430837494885949696427. For this input the Liang's output is correct!! Don't You think?

Wojciech

UFP2161 · Post by **UFP2161** » Tue Jun 15, 2004 8:51 pm

You are right.. I (and probably he) read input as %lld.. should be %llu.. but judge apparently does not test this fact (maybe they really meant less than 19, and not less than or equal to)

Master · Post by **Master** » Sat Jul 17, 2004 12:09 pm

Hi everybody,
I have read the problem several times and unable to understand this. Any one please help me to understand the problem specially the I/O.

Thanks in advance.
M H Rasel
CUET Old Sailor

Sanny · Post by **Sanny** » Sat Jul 17, 2004 3:10 pm

Hi,
In this problem u have a set of numbers containing three's powers.
S = { 1,3,9,27,81,..........}.
Now if u construct different subsets of this set and sort them ascending by the sum of their elements then u get
{ }
{ 1 }
{ 3 }
{ 1,3 }
{ 9 }
{ 1,9 }
{ 3, 9 }
{ 1, 3, 9 }
{ 27 }
...................
..................
In this problem u have to determine the n'th subset obtained in this manner.
Hope it helps.

Master · Post by **Master** » Mon Jul 19, 2004 5:44 am

Thanks for help. But yet I am strugling. How can i solve this problem with less time. Is there any equation or something.

Please Help.
M H Rasel

Master · Post by **Master** » Mon Jul 19, 2004 5:47 am

Thanks for help. But yet I am strugling. How can i solve this problem with less time. Is there any equation or something.

Please Help.
M H Rasel

Sanny · Post by **Sanny** » Tue Jul 20, 2004 11:54 pm

Hi,
If you write the subsets for first few values of n, you can see that for n=3 to n=4 3 is common. Again, for n=5 to n=8 9 is common. For n=9 to n=16 27 is common. I think you can utilize this fact.

Master · Post by **Master** » Wed Jul 21, 2004 6:39 am

Thanks a lot

I will try it

sclo · Post by **sclo** » Thu Feb 16, 2006 11:12 am

Just think about binary expansion of n

sclo · Post by **sclo** » Thu Feb 16, 2006 11:19 am

This are the correct output from my AC program:

Code: Select all

{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381059609, 282429536481, 847288609443, 2541865828329, 68630377364883, 617673396283947, 1853020188851841, 5559060566555523, 150094635296999121, 450283905890997363, 4052555153018976267, 36472996377170786403, 109418989131512359209, 984770902183611232881, 2954312706550833698643, 26588814358957503287787, 19383245667680019896796723, 58149737003040059690390169, 174449211009120179071170507, 523347633027360537213511521, 4710128697246244834921603689, 14130386091738734504764811067 }
{ 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 10460353203, 31381059609, 94143178827, 282429536481, 7625597484987, 617673396283947, 16677181699666569, 12157665459056928801, 36472996377170786403, 2954312706550833698643, 79766443076872509863361, 239299329230617529590083, 717897987691852588770249, 58149737003040059690390169, 174449211009120179071170507, 1570042899082081611640534563, 14130386091738734504764811067, 1144561273430837494885949696427 }

OJ Board

10669 - Three powers

10669 - Three powers

that's odd

10669 - Cant Understand the problem