11752 - The Super Powers

All about problems in Volume 117. 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
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11752 - The Super Powers

Post by Angeh » Thu Feb 18, 2010 6:10 pm

Any Ideas How To solve This Problem efficiently ....
and How To handle The overflow?
any help is appreciated.....:)
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11752 - The Super Powers

Post by arifcsecu » Sun Feb 21, 2010 9:02 pm

How can i solve this ?
I have got TLE.

Please help any body.
Try to catch fish rather than asking for some fishes.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: Goods2010-02-15-fifty-11

Post by arifcsecu » Sun Feb 28, 2010 12:45 am




// What is this ..................
It is very important forum for the programmers but not for others ...............
Try to catch fish rather than asking for some fishes.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11752 - The Super Powers

Post by Jehad Uddin » Sun Jul 04, 2010 6:41 am

Take the composite powers of nos upto 2^16
2^4
2^6
...
3^4
3^6
..
4^4
4^6
..
To handle overflow before multiplying just chek it log(no1)+log(no2)<64log(2)

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11752 - The Super Powers

Post by plamplam » Thu Jun 23, 2011 7:06 am

My best for this problem is 0.032 (The best for this problem is 0.028 :D :D ). And I didn't even optimize my code, no I/O opt nothing. (May be someday I can beat the best record with I/O Optimization :D). I am not going to tell you my algorithm....no way guys but I can give you hints. You have to print a total of 67385 lines(including 1). And think a bit, what property would a number have if it is the power of at least two different positive integers? For example 16 = 2^4 and 4^2 and 729 = 3^6 and 9^3 and 27^2 etc. No more hints for you, you must solve this problem by yourself :) Be assured, you won't get WA or TLE if your algo is correct and efficient and you are printing exactly 67385 lines(In increasing order). (You can check this by increasing a counter variable starting from 0 whenever you are printing a line and later just print that counter variable :) ) :lol:
Last hint(probably the most useful one) : You have to print all the numbers in ascending order as specified in the description. However this does not necessarily mean that you have to FIND all such numbers in ascending order.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11752 - The Super Powers

Post by plamplam » Thu Jun 23, 2011 7:48 am

And @Angeh the best way to handle overflow in this problem is by using log/ln (any one will do), but I didn't use the log/ln function in my program :D
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 11752 - The Super Powers

Post by outsbook » Sun Jul 15, 2012 4:33 pm

For check Overflow
You can use

Code: Select all

int bit = 64;
int power= ceil(bit  / (log(powerBase)/log(2)));
Example:
1. If powerBase=3 then power=41 (i.e. the maximum power of 3 is 40, 3^40 < 2^64-1(unsigned long long range)). 3^41 is overflow at 64 bit integer.

2. If powerBase=5 then power=28 (i.e. the maximum power of 5 is 27, 5^27 < 2^64-1(unsigned long long range)). 5^28 is overflow at 64 bit integer.
:D :D :D
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Post Reply

Return to “Volume 117 (11700-11799)”