MyVeryLongCake
SRM 617 · 2013-12-22 · by dolphinigle
Problem Statement
You are expecting some friends. You are going to cut the cake into multiple pieces before the friends arrive.
When the friends arrive, you will divide the cake among them, using the following procedure: starting at the beginning of the cake, you will first give some consecutive pieces to your first friend, then some consecutive pieces to your second friend, and so on.
Of course, you want to be fair. That is, each of your friends should receive the same total amount of cake. (The number of pieces may be different for different friends, but the sum of their lengths must be the same.)
As we stated above, you want to cut the cake before your friends arrive. However, you don't know how many friends will actually come. You only know that their count will be a divisor of n smaller than n.
You are given the
Constraints
- n will be between 2 and 1,000,000,000, inclusive.
6 Returns: 4
The best possible solution is to cut the cake into 4 pieces. Let's call the pieces A, B, C, and D, in order. Their lengths will be 2, 1, 1, and 2. As n=6, there will be 1, 2, or 3 friends. If there is just one friend, she gets all four pieces. If there are two friends, the first gets A+B and the second gets C+D. If there are three friends, the first gets A, the second gets B+C, and the third gets D. Note that the order of parts matters. For example, dividing the cake into parts of length 2, 1, 2, and 1 is not a valid solution.
3 Returns: 1
In this case, the only possible number of friends that will come to your house is 1. Hence, you don't even need to cut the cake, simply leave it in one piece.
15 Returns: 7
You are expecting 1, 3, or 5 friends.
1000000000 Returns: 600000000
223092870 Returns: 186597510
Submissions are judged against all 184 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MyVeryLongCake with a public method int cut(int n) · 184 test cases · 2 s / 256 MB per case