Hide

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

Hide

Please log in to submit a solution to this problem