POWTOW - Power Tower City

You are living in a city build entirely of power towers such as 3^3^3 and 10^10^10^10. To enter a building you must type the last 9 digits of the number represented by the tower, written in decimal form, on a keypad next to the main entrance. You are not sharp enough at mental maths, but you can write a handy program to bring along in your pocket.

A power tower is defined as repeated exponentiation. We write this using Knuth's up-arrow notation as: e↑↑a = e^e^...^e (a terms). Remember that ^ (exponentiation) is right associative. For example: 2↑↑4 = 2^2^2^2 = 2^(2^(2^2)) = 2^2^4 = 2^16 = 65536, and 3↑↑1 = 3. The value of a tower of height 0 is 1.


The first line contains integer C in [0..1000], the number of test cases.

Then follows C lines, each with integers e,a in [0..2147483647]. (non-negative 32-bit integers).


For each testcase output e↑↑a, or if the output has more than 9 digits, output "..." and then the last 9 digits.


0 0
2 5
993306745 75707320


hide comments
suhang: 2012-04-10 03:01:43

@Thomas Dybdahl Ahle
Can you give me some test i'm getting WA?

pulkit: 2012-04-09 19:34:06

@Thomas: My code seems to work correctly.. Can't really find any corner case...
A hint would be useful...

Anirvan Sarkar: 2012-02-07 11:36:05

@Thomas Dybdahl Ahle:
Thanks for pointing out my mistake. It helped me to find the bug in my code after many WA.

Thomas Dybdahl Ahle: 2012-02-04 00:30:50

@Anirvan Sarkar: You fail "2 20"
@Marin Tomic: You fail "0 1"
@Santiago Palacio: I have made the problem description more clear.

Santiago Palacio: 2012-02-04 00:19:52

Yes, i know you can deduce it from that, but what i say is that with problems like this, it's not always that obvious and should be more explicit.

Mitch Schwartz: 2012-02-04 00:19:52

@Santiago: 2^2^2^2 = 2^2^4 = 2^16 = 65536 is unambiguous. You can notice that ((2^2)^2)^2 would make 256.

Anirvan Sarkar: 2012-02-04 00:19:52

@Thomas Dybdahl Ahle

Can you tell me for which test case i'm getting WA?

Santiago Palacio: 2012-02-04 00:19:52

It's 2^(2^(2^2))) right? (I think the problem statement is not fully clear about it, as it could be (((2^2)^2)^2).

Thomas Dybdahl Ahle: 2012-02-04 00:19:52

@numerix: np. But I'm wondering if the bug shows that your method isn't strong enough for general mods?

Thomas Dybdahl Ahle: 2012-02-04 00:19:52

Hi numerix, you are right. Test data was wrong for 0||(2n). It's fixed now. Thank you.
I can tell you that you still report "10 3" as "...000000001" which is clearly wrong.

Last edit: 2011-11-23 22:01:38

Added by:Thomas Dybdahl Ahle
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64