# UVa 10970

Jump to navigation Jump to search

## Summary

A chocolate bar is a ${\displaystyle MN}$ rectangle, composed of unit squares. Determine, how many straight-line cuts are necessary to split it into unit-square pieces. Each cut can only divide one connected piece of chocolate into two.

## Explanation

Note the following facts:

• In the beginning we have one piece of chocolate.
• At the end we want to have ${\displaystyle mn}$ pieces.
• Each cut divides one piece into two, thus the number of pieces increases by one.

Thus we will need exactly ${\displaystyle mn-1}$ cuts regardless of the way we cut the chocolate.

A slower solution:

The constraints are so low that solutions using dynamic programming/memoization will be accepted. The idea is: for each piece chocolate not larger than ${\displaystyle m\times n}$ compute the smallest number of cuts needed. If ${\displaystyle f(x,y)}$ is the minimum number of cuts for a ${\displaystyle x\times y}$ chocolate bar, we get:

• ${\displaystyle f(1,n)=n-1}$
• ${\displaystyle f(m,n)=\min _{1\leq k\leq m-1}[1+f(k,n)+f(m-k,n)]({\mbox{for }}m>1)}$

## Input

2 2
1 1
1 3
5 5
5 10
10 5


## Output

3
0
2
24
49
49