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?

\includegraphics[width=0.4\textwidth ]{sample2}
Figure 1: Illustration of a solution to Sample Input 2, showing the original $10$-by-$10$ chocolate bar split three times into pieces of size $10$-by-$2$, $10$-by-$5$, $3$-by-$3$ and $7$-by-$3$. Giving Alice the $10$-by-$5$ and $7$-by-$3$ pieces, she gets a total of $50 + 21 = 71$ chocolate cells.


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 the minimum number of splits needed to achieve the desired division of chocolate.

Sample Input 1 Sample Output 1
3 10 9
Sample Input 2 Sample Output 2
10 10 71
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.2medium
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in