# UVa 10970

From Algorithmist

## 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]

- UVa 366 http://uva.onlinejudge.org/external/3/366.html (generalization of the problem)