Cocoa Coalition
Time limit1sMemory limit512 MB
Break an n by m chocolate bar with straight-line cuts into pieces that can be grouped into one pile of a cells and one of b cells, minimizing the number of cuts.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Brute force, Implementation
- Solved
- No attempts yet
Problem
Alice and Bob decide to share a chocolate bar, which is an n by m rectangular grid of chocolate cells. They agree that Alice gets a < n · m pieces and Bob gets b = n · m − a pieces. To split the bar, they repeatedly take a single piece of chocolate and break it either horizontally or vertically, producing two smaller pieces. See Figure C.1 for an example.
What is the minimum number of splits needed to divide the n by m chocolate bar into two piles of a and b chocolate cells?
Figure C.1: An illustration of a solution to Sample Input 2. The original 10 by 10 chocolate bar is 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 yields a total of 50 + 21 = 71 chocolate cells.
Input
The input consists of a single line containing the three integers n, m, and a (1 ≤ n, m ≤ 106, 1 ≤ a < n · m).
Output
Print the minimum number of splits needed to achieve the desired division of the chocolate.