UVa 10970

From Algorithmist
Jump to navigation Jump to search

10970 - Big Chocolate[edit]

Summary[edit]

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.

Explanation[edit]

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:

Solutions[edit]

Input[edit]

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

Output[edit]

3
0
2
24
49
49

See Also[edit]