The Rise and Fall of Power

All submissions for this problem are available.
The following problem appeared in the CodeChef March '09 Challenge.
Johnny was asked by his math teacher to compute n^{n} (n to the power of n, where n is an integer), and has to read his answer out loud. This is a bit of a tiring task, since the result is probably an extremely large number, and would certainly keep Johnny occupied for a while if he were to do it honestly. But Johnny knows that the teacher will certainly get bored when listening to his answer, and will sleep through most of it! So, Johnny feels he will get away with reading only the first k digits of the result before the teacher falls asleep, and then the last k digits when the teacher wakes up.
Write a program to help Johnny to compute the digits he will need to read out.
Input
The first line contains t, the number of test cases (about 30000). Then t test cases follow.
Each test case consists of one line containing two numbers n and k (1 ≤ n ≤ 10^{9}, 1 ≤ k ≤ 9). It is guaranteed that k is not more than the number of digits of n^{n}.
Output
For each test case, print out one line containing two numbers, separated by a space, which are the first and the last k digits of n^{n}.
Example
Input 2 4 2 9 3 Output 25 56 387 489
Author:  admin 
Tags  admin 
Date Added:  18032009 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
Does the given time limit indicate compile time? Or the time for producing the output?
Is there anyway to limit the input size? i could not use double (in java) for such a big number. Mine should work for n value till 140 (where n^n is within double limit). Any help please
@jagan
Have you considered using java.math.BigInteger ?
Zach
@jagan It is possible to code this in C . You can't possibly store that large a number in a double. Think of other ways to get the required result.
Any suggestions for testing
long long in c/c++ can store
Sorry, I was unclear. I was
Hi, my solution is being
@codechef admin: My
There is a problem with
There is a problem with overloading the pow() function.
@aniruddha: thanks :). It has
hello admin.. I am new to
hello admin..
I am new to codechef..I am working on my first problem "The Rise and Fall of Power"..I saw in the FAQ's that the file should be names Main.java...and i think that, the only file my solutions should have is Main.java..no more class files...please correct me if i am wrong..
thank, Jaydip
Yes, that is correct. Name
Yes, that is correct. Name your class as Main.
hello admin, I was working on
hello admin,
I was working on this problem using Java (1.5), I am testing my solution for larger numbers like 1000000000...but i think due to the known bugs as listed below, the performance is getting too slow...is it possible to solve this using Java...
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
Hello Admin, Please check
Hello Admin,
Please check my submitted solution and inform me if the way of taking user inputs one case at a time and displaying the result output to the console cause the result "Time limit exceeded"...or something else..
Thanks,
Jaydip
hey suppose if thwe input
hey suppose if thwe input is
1
100 5
then shud the output be
10000 00000
or
10000 0
Any ideas??
hi admin .. isn't cout , cin
hi admin .. isn't cout , cin , iostream recognizable in c++ with linux . i am using windows . any substitute??it is giving compilation error but program is compiling successfully in my pc
They work perfectly fine
They work perfectly fine (though are extremely slow, so you really shouldn't use them). Perhaps you are doing something like forgetting using namespace std; or something else to cause a compile error.
Hi all, I am getting time out
Hi all,
I am getting time out result.
Is it possible to get single threaded optimal solution for this problem.
Hi all, Is anyone get the
Hi all,
Is anyone get the single threaded correct solution for this problem..
Hi all, Is it possible single
Hi all,
Is it possible single threaded accepted solution for this problem.
I have submitted a solution which is showing time out.
I optimize my code enough. still it is showing same.
Should i go for multithreading??
plz give me hints..
You never need to write a
You never need to write a multithreaded solution for any of these problems.
Hi Admin, I have tried
Hi Admin,
I have tried multiple solutions to this problem. As discussed in the blog, if my solution is "numericallycorrect" and which it is, it should not give WAs. I see that there was some problem with the test data earlier. Is it resolved ?
My output for the input set that Shishir Mittal has posted above matches with his. So there's a stronger reason to believe that my code is giving correct output.
Please check and let me know.
ADMIN ... i am getting
ADMIN ... i am getting runtime error for my code ... can u plz tell why ... it's working on my system
@Abhyajit Please read the FAQ
@Abhyajit Please read the FAQ and www.codechef.com/wiki
Hi Aniruddha, I have been
Hi Aniruddha,
I have been working on this problem for very long time. Its working fine on my computer even for very large values. But here its saying wrong answer. I think the error must be with the first part of output i.e the first k digits of the number. It would be very helpful if you can tell me for what test cases its failing. Or any suggestion in this direction would be helpful.
Thanks,
Arun
in Java if an exception like
in Java if an exception like arrayindexoutofbound occurs in a submitted solution will the judge show it as WA or run time error ??
That is exactly what runtime
That is exactly what runtime error means.
i have got the idea of the
i have got the idea of the problem clear..my code is giving correct output for some cases but for some cases there is rounding off error as i am using log to solve the prob.i have read abt adding epsilon to counter tht error in uva forum...bt didnt get it..can anyone expain abt this a bit more..giving some example or some url abt it...
@admin I am trying to submit
@admin I am trying to submit my solution in php. Can you please tell me what error I am doing. The code runs perfectly in my laptop. Can I post my code here?
I submitted solutions for some other problems which takes a lot of memory for php in comparison to c. for same algo, I also had the timeout error for the same code of C/C++/Jave (Successfully compiled programs) written by some1 else when I change the syntax to PHP
can any one plz confirm that
can any one plz confirm that the output given by sishir mittal given above is correct or not
my output is matching with his output by i am getting WA. So plz confirm whether his output is corret or not
my program gives the same
my program gives the same output as given by shishir mittal but i am getting WA.
please anyone confirm whether the output is correct or not
@Alok I am also getting the
@Alok
I am also getting the same o/p but its showing WA....
@admin Is it possible to
@admin
Is it possible to code this problem in Java? As using Long we can store 10^18. and double 10^308. here we have to deal with 10^9 raised to 10^9.
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
It is impossible to calculate
It is impossible to calculate the full value of n^n in any language and get accepted within the time limit. That is not the approach you are supposed to take in this problem.
@ Admin, I am unable to get
@ Admin,
I am unable to get any idea for this problem . Plzzzzzzzzz try to provide the tutorial for this problem :P .
@stephen so some other
@stephen
so some other approach is to be used to calculate full value or there is no need of calculating full value(answer could be obtained without calculating full value)?
As I said, calculating the
As I said, calculating the full value is impossible. You must use another approach.
i am getting the right
i am getting the right outputs but a run time error. I have coded in simple c++ but used recursion to calculate the last k digits. Is it because of the recursion that I am getting runtime error?
I am facing a precision
I am facing a precision problem here. Not able to get the last digit from the first digits. I have tried 6 approaches but could only get the precision till first 8 digits at best. Any suggestions.
Chefs, Need a clarification:
Chefs, Need a clarification: Are all the 30000 testcases required to complete within the 4 allowed seconds? Or is it a maximum of 4 seconds per test case?
FAQ
FAQ
faq! thanks, should've done
faq! thanks, should've done that first.
Its interesting how there isn't even a single successful Java solution to this problem. Time to abandon the libraries I suppose  too slow!
Can any one provide me the
Can any one provide me the o/p for the large value actually i wanna know whether my programe is running correct or not.
leg eg: give me the o/p for K=84246793
You can use Wolfram
You can use Wolfram Alpha(http://www.wolframalpha.com/) to check your answers
@BorT btw K has to be <=9
@BorT btw K has to be <=9
Dangit, more java
Dangit, more java optimizations, still out of time.
Hey Stephen, you're a Java dude. and I see you don't have this problem in your list, want to share ideas?
@rockypg unable to find the
is there any need for error
@admin N=84246793(
@admin
N=84246793( random)
provide me output. for any large number i want to check
for N=594859374,K=9 o/p
for N=594859374,K=9
o/p =321824352 095142400
is this o/p is correct can any one can help
for N=594859374,K=9 o/p
for N=594859374,K=9
o/p =321824352 095142400
is this o/p is correct can any one can help
AC Outputjunk@debian:~$ echo
AC Outputjunk@debian:~$ echo 1 19423474 8  ./a.out
16307491 26110976
junk@debian:~$ echo 1 19423474 9  ./a.out
163074912 826110976
junk@debian:~$
@everyone i have method to
@everyone
i have method to calculate higher n^n but while we calculate 10^9 is near about 9*10^9 decimal digit and the code cross memory usage limit then how we can store it in memory...???
Trying to calculate the full
Trying to calculate the full value is impossible. You have to figure out a way of just calculating the digits you need.
@Admin : I have been trying
@Admin :
I have been trying this problem for quite a while now ... have made a few sumissions. I am getting "wrong answer" each time. Can you please provide me with some help / hint ?
Thanks :)
@ admin : I tried a new
@ admin :
I tried a new approach to the solution. My code ran for a longer time but yet again  I got "Wrong Answer" . Can u plzz help me out ?? Where am i going wrong ?
@admin if the input is 10
@admin
if the input is
10 3
then should the answer be
100 000
or
100 0
The problem works fine on my
The problem works fine on my system but i keep getting WA here..
Please help..am I missing some special test cases ??
@admin my submission is
@admin
my submission is giving a run time error
plz tell me the reason
Hello admin can u just have a
Hello admin can u just have a look at this code I am sure that is right but it gives wrong answer!!
http://www.codechef.com/viewsolution/314425
Hello Admin Please check the
Hello Admin
Please check the above link!!
Same question again . Should
Same question again .
Should the answer for 10 3 be 100 000 or 100 0 ??
I think i am having precion
I think i am having precion problems, any hints i am using double and unsigned long long int . Calculating only first k and last k digits. my solution is at http://www.codechef.com/viewsolution/352153
@ Admin, could you please let
@ Admin, could you please let me know what is the problem in my submitted solution, since I am getting WA which I think shouldn't be the case. http://www.codechef.com/viewsolution/357085
@admin please check these two
@admin please check these two links
http://www.codechef.com/viewsolution/349188
http://www.codechef.com/viewsolution/351625
Hey... my code is in
Hey...
my code is in python... Have tried a lot of time, the algo is correct and is executing within the time limit... Have tried most of the test case and get the correct answers even for the worst ones. dont know what the problem is.... can you pls help!!!!
@admin pls check this
@admin pls check this link
http://www.codechef.com/viewsolution/362942
can u pls tell me where i'm going wrong.. it seems to be workin fine on my comp...
@^^ oops i dint mean to make
@^^ oops i dint mean to make it so big.. :P
To Admins: I don't know how
To Admins:
I don't know how far the test cases are correct, but for first k digits I am using first k digits of 10^(fraction(nLog10(n))). Here are my observations:
Any number like n=457474575, 10^(fraction(nLog10(n))) = 2.7866096861492488724505088885778 as per windows calculator. But, in my code, the long double precision is only upto 15 places of decimal. So, when Log10 (15 places of decimal) is multiplied with a 9 digit number, i.e. 457474575, the correctness of (fraction(nLog10(n))) is only upto 6 places of decimal. Hence, when I raise the fraction to 10^fraction, I have a result which is correct to only 4 places of decimal.
I almost broke my head for the last two days to make the 10^fraction correct upto 9 places, but couldn't succeed. After repeated attempts, I was successful to be precise upto 8 places of decimal.
Guess what, when I submitted the 8 places decimal precise code, my code was repeatedly rejected as "wrong answer", but when I submitted the 4 place precise answer, my code was accepted.
For n = 457474575,
Windows calculator ans = 2.7866096861492488724505088885778 (precise upto 31 places of decimal)
8 places precise ans = 2.78660965 (rejected multiple times)
4 places precise ans = 2.78661176 (accepted)
I don't know how the test cases are determined, but here I can definitely say they are faulty here. I am new to CodeChef platform, and I was redirected to this puzzle from Directi carrers page. I am sorry to say that I am utterly disappointed as a new user, I worked hard on this problem for 2 days to make it 8 places precise, only to find those test cases are not considered here.
@Ujjwal you should read
@Ujjwal you should read this
http://discussed.codechef.com/showthread.php?t=115
@Ujjwal  I'm afraid there is
@Ujjwal  I'm afraid there is nothing wrong with the test cases (which do include ones like you mentioned). I'm not sure what you are using to compile your code, but on codechef and most compilers, long double has 18 decimal places of accuracy, compared to a normal double which has 15.
Your accepted code correctly outputs 278660968 for the test case you mentioned. If you wrote other code which you think has more accuracy, then that code must have a bug in it.
hi stephen! Thanks for your
hi stephen! Thanks for your revert. I am using Microsoft Visual Studio 2008: Visual C++ as my compiler. Please suggest me any good compiler on windows. Also, here I found out that standard long double is 15 digits precise only, thats why the confusion: http://msdn.microsoft.com/enus/library/s3f49ktz%28VS.90%29.aspx
@vivek, I figured out that and corrected it later
That is one of the special
That is one of the special cases (see http://en.wikipedia.org/wiki/Long_double)
If you want to ensure that you are getting the same results as the judge then you should use the same compiler (gcc4008 or gcc432), for which you can find compatible IDEs at http://en.wikipedia.org/wiki/GNU_C_Compiler .
Hey is the current
Hey is the current requirement 6 digits or 9 digits of precision coz in that forum discussion it says only 6 digits required. also could the admin tell me if im failing in 1st k last k or both digits please?
Somebody please tell me why
Somebody please tell me why am I getting a wrong answer for this question!!
Internal Error. Can not
Internal Error. Can not submit your answer now. Please try after some time.
why is the judge showing me
why is the judge showing me wrong answer ? is the internal error still persistent ?
Nope, you are getting wrong
Nope, you are getting wrong answer because your answer is wrong.
@all what will be the output
@all
what will be the output of
1 5
is it
00001 00001
or
1 00001
or
1 1
???
The 'Input' section clearly
The 'Input' section clearly says that test case will not be provided.
n k 34
n k
34 9 : 117566389 909569536
23 8 : 20880467 32910567
92 9 : 466101087 933364736
199 7 : 2963208 3999799
234232 9 : 943982129 347762176
3476566 9 : 226270832 024828416
569999999 9 : 349261536 429999999
999999999 9 : 367879441 999999999
567891234 9 : 191465113 712180736
457474575 9 : 278660968 380859375
@Stephen :can you check
@Stephen :can you check whether above soln are correct or not??
@admin: Where i am doing
@admin: Where i am doing wrong. http://www.codechef.com/viewsolution/426502.. Unable to verify for larger input.. Getting rite answer as far as calc supports...
@Manohar  one of your
@Manohar  one of your results is off by 1. That suggests whatever approach you are using is not precise enough.
@nikhil  you can verify whether your approach will work for larger input. How many digits is log10(n) correct to? When you multiply that by a 9 digit number, how many digits will your number be accurate to? Is that enough?
Is it really so easy
Is it really so easy problem?? Why i am unable to do this even i have done problem of level 4. But no precise idea for this level 1 problem :(..
@admin, I think my Python
@admin,
I think my Python code is fast and precise enough to be accepted within time limit but gives TLE.
http://www.codechef.com/viewsolution/435643
what astonishes me more is there are no python AC, all in c/c++ :O
everytime WA dnt know whats
everytime WA dnt know whats the prob please help!!!!!
My code: http://www.codechef.com/viewsolution/439918
does a 0(n) algo work for
does a 0(n) algo work for this ques
is 4 sec time limit for all
is 4 sec time limit for all testcases or for each testcase
@all....how can we find the
@all....how can we find the last k digits....plzz....do reply....
Can anyone tell me where is
Can anyone tell me where is my code giving WA : http://www.codechef.com/viewsolution/474576
please check the output for
please check the output for n=5 and k=4... if anyone gets a wrong answer please reply here... i was getting an exceptional wrong answer for this input.. is anybody else getting this exceptional case.. only with wrong answers reply.
Hi admin, Can you give me a
Hi admin,
Can you give me a hint on where am I going wrong.
1. Is my algorithm incorrect and I need to think for a different solution or
2. I just need to tweak my algorithm?
Here is my solution: http://www.codechef.com/viewsolution/537865
Please guide.
@admin or anyone who has
@admin or anyone who has solved the problem
please guide where am I going wrong. At the least, please tell me if I am in the wrong direction so that I could stop wasting time. I am getting TLE.
My solution: http://www.codechef.com/viewsolution/539127
Thanks..
Can somebody tell what is the
Can somebody tell what is the wrong with this result?
11
34 9
23 8
92 9
199 7
234232 9
3476566 9
569999999 9
999999999 9
567891234 9
457474575 9
1000000000 9
117566389 909569536
20880467 32910567
466101087 933364736
2963208 3999799
943982129 347762176
226270832 024828416
349261650 429999999
367880063 999999999
191464928 712180736
278661176 380859375
100000000 000000000
dono y getting WA i made a
is n=0 a valid input for the
whats wrong in
@admin  Do we require High
someone plz provide hint abt
unable to submit solution
I am trying to extract the
is this just level 1 problem?
How to get past through this
Can anyone tell me why below
@Admin... I have tested my
Admin pls help, why am I
@admin please give a hint
hi admin My answer has been
anyone pls i need some
@tarun483 if ur program gives
I am unable to use cin & cout
@suryadharani using namespce
not able to submit this
@admin. is a solution
http://www.codechef.com/views
#include #include int
admin pls tell what is error
http://glug.nith.ac.in/paste/
http://www.codechef.com/views