UVa 107

From Algorithmist
Jump to navigation Jump to 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 different heights in all cats.

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:


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

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.
  • Take care of precision issues in the use of log().
  • Consider modulus operator (%) to test A/T is an integer or not in integer-only implementation.

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]