# UVa 10970

## Summary

A chocolate bar is a $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 $mn$ pieces.
• Each cut divides one piece into two, thus the number of pieces increases by one.

Thus we will need exactly $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 $m\times n$ compute the smallest number of cuts needed. If $f(x,y)$ is the minimum number of cuts for a $x\times y$ chocolate bar, we get:

• $f(1,n)=n-1$ • $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