CODEWITHSUNDEEP
c++algorithm
user3840069
user3840069

Reputation: 765

Minimum cuts with each cut passing through 2 points on circle

There are N persons and we wishes to give only one piece of cake to each person. Bob has his own way of maximizing number of pieces. For each cut, he tries to make maximum possible smaller pieces after that cut. The cake is circular and each cut follows a straight line that passes through the circle twice. There will be no half-cuts or semi-cuts.

what is the minimum number of cuts he should make so that every person gets at least one smaller part of the cake. (With this kind of distribution, every person will not get same size of cake and he is not bothered of it.)

Example : Let N=3 then answer is 2.

Note : Passes through circle twice mean that the cut doesn't stop in between. It starts at one point on circle, and ends at some other point. It is not necessary that cut has to pass through center for sure

Here is my code that I tried : 

typedef unsigned long long int ulld;
ulld n;
cin >> n;
ulld steps = 0;
ulld currentAmount = 1;
while (currentAmount < n) steps++, currentAmount <<= 1;
cout << steps << endl;

N can go upto 10^12. So I want O(log n) appraoch.

Upvotes: 1

Views: 164

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

The number of pieces f(k) that can be made with k cuts is a somewhat famous problem, whose solution is f(k) = k*(k+1)/2 + 1. You could have found that sequence yourself by working small examples and invoking the search function on OEIS. Solving for f(k) = n, we get k = ceil((sqrt(8*n - 7) - 1)/2).

Upvotes: 1

Related Questions