# UVa 107

From Algorithmist

## 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:

- 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.

## 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