Eat All the Brownies

This post is in reference to SPOJ 17626. Eat all the brownies CUTCAKE.

The question is: to divide a plane into X pieces, how many lines (cuts) are needed? Magically, the answer is found on page 499 of Knuth’s Concrete Mathematics 2nd Ed. (or p485 in this PDF), and is as follows:

regions = (tabular{000}{00}{cuts 0}) + (tabular{000}{00}{cuts 1}) + (tabular{000}{00}{cuts 2})
(tabular{000}{00}{cuts 0}) = 1
(tabular{000}{00}{cuts 1}) = cuts
(tabular{000}{00}{cuts 2}) = {cuts!}/{(cuts-2)! * {2!}} = {cuts * (cuts - 1)}/2

N.B. (tabular{000}{00}{n k}) is the binomial coefficient function.

So this solves for regions given the number of cuts. But in this problem we’re to solve it the other way around; this is done via binary search.

My solution is in git and here:
Continue reading