UVa 10079

From Algorithmist
Jump to navigation Jump to search

10079 - Pizza Cutting[edit]

Summary[edit]

Given the number of straight cuts you can make on a pizza, find the maximum number of pieces in which the pizza can be divided.

Explanation[edit]

If we make no cuts at all, we still have the whole pizza to eat. Hence . Each new cut can possibly intersect all the previous cuts. It means that After lines have been drawn, the nth line can intersect each of these, so it has intersections, and hence new regions, so the recurrence we get is . Solving this recurrence gives the formula and hence .

Implementation[edit]

  • Use 64-bit integers (long long in C++) to avoid overflow.

Input[edit]

0
5
10
210000000
-100

Output[edit]

1
16
56
22050000105000001