10669 - Three powers

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
bmouse001
New poster
Posts: 3
Joined: Mon Jun 14, 2004 2:41 pm

10669 - Three powers

Post by bmouse001 »

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 }

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 »

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
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

that's odd

Post by sohel »

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

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
New poster
Posts: 3
Joined: Mon Jun 14, 2004 2:41 pm

Post by bmouse001 »

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
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

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 :D

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

10669 - Cant Understand the problem

Post by Master »

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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny »

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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny »

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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

Thanks a lot

I will try it

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Just think about binary expansion of n

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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 }

Post Reply

Return to “Volume 106 (10600-10699)”