Problem C
Cocoa Coalition
Alice and Bob decide to share a chocolate bar, which is an $n$ by $m$ rectangular grid of chocolate cells. They decide that Alice should get $a < n \cdot m$ pieces and that Bob should get $b = n \cdot m - a$ pieces. To split the chocolate bar, they repeatedly take a single piece of chocolate and break it either horizontally or vertically, creating two smaller pieces of chocolate. See Figure 1 for an example.
What is the minimum number of splits that Alice and Bob need to perform in order to split the $n$-by-$m$ chocolate bar into two piles consisting of $a$ and $b$ chocolate cells?
Input
The input consists of a single line, containing the three integers $n$, $m$ and $a$ ($1 \le n, m \le 10^6$, $1 \le a < n \cdot m$).
Output
Output the minimum number of splits needed to achieve the desired division of chocolate.
Sample Input 1 | Sample Output 1 |
---|---|
3 10 9 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
10 10 71 |
3 |