UVa 10970

From Algorithmist
Jump to: navigation, search

10970 - Big Chocolate[edit]

Summary[edit]

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[edit]

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)

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]