UVa 107

From Algorithmist
Jump to: navigation, search

107 - The Cat in the Hat[edit]

Summary[edit]

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.

Explanation[edit]

  • 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: \left({\frac  {N}{N+1}}\right)^{{M-1}}={\frac  {B}{A}}


  • 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:
  • 1+N+N^{2}+\ldots +N^{{M-2}} AND A\left(1+{\frac  {N}{N+1}}+{\frac  {N}{N+1}}^{2}+\ldots {\frac  {N}{N+1}}^{{M-1}}\right)

Gotchas[edit]

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

Input[edit]

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

Output[edit]

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

Solution[edit]