MyLongCake
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 100,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
15 Returns: 7
You are expecting 1, 3, or 5 friends.
12 Returns: 8
100000 Returns: 60000
Submissions are judged against all 168 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MyLongCake with a public method int cut(int n) · 168 test cases · 2 s / 256 MB per case