# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

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.

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?

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.

Input | Output |
---|---|

3 10 9 | 1 |

Input | Output |
---|---|

10 10 71 | 3 |

This NCPC 2019 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NCPC website.

73% Solution Ratio

ThePtrocanferEarliest,

bugsbunnyFastest, 0.0s

ArcturusLightest, 131 kB

pasha009Shortest, 356B

Login to submit