10970 - Big Chocolate
A chocolate bar is a 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.
Note the following facts:
- In the beginning we have one piece of chocolate.
- At the end we want to have pieces.
- Each cut divides one piece into two, thus the number of pieces increases by one.
Thus we will need exactly 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 compute the smallest number of cuts needed. If is the minimum number of cuts for a chocolate bar, we get:
2 2 1 1 1 3 5 5 5 10 10 5
3 0 2 24 49 49