UVa 107

From Algorithmist

Contents 1 107 - The Cat in the Hat 2 Summary 3 Explanation 4 Gotchas 5 Input 6 Output

[edit] 107 - The Cat in the Hat

• http://acm.uva.es/p/v1/107.html

[edit] Summary

We need to find two integer numbers N and M, where N is the number of cats inside each (non-smallest) cat's hat and M is the number of cats with different heights.

[edit] Explanation

• In order to solve this problem we have to find the two integers N and M. We consider the height of the first cat = A and the number of working cats = B. Using some simple math logics we can write this equation:

• We search M in the interval (2, HighValue) and binary search for R such that R^{M - 1} = B. We do the same for T such that T^{M - 1} = A. If T = R + 1 then we find N = R. With the curent values of N and M we compute the output numbers:

• AND

[edit] Gotchas

• Take care of "1 1" input case. Solving this case doesn't work with the upmentioned algorithm.
• I used HighValue = 200 in AC code.

[edit] Input

1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0

[edit] Output

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
29524 4017157
615441 1931252289
21 369
6 127
9 217