LandSplitter
SRM 774 · 2020-01-09 · by misof
Problem Statement
A lord owned a piece of land with area N. He wanted to give parts of this land as rewards to his subjects, so he decided that he will split the piece of land into one or more pieces in such a way that the size of each piece will be between A and B, inclusive. But splitting pieces of land is regulated by the king of this country, as follows:
- Each piece of land must always have a positive integer area.
- For all X, Y: The owner of a piece of land of size X+Y may split it into two pieces of size X and Y, but if they do, they have to pay the king X*Y in taxes.
- For all X, Y, Z: The owner of a piece of land of size X+Y+Z may split it into three pieces of size X, Y, and Z, but if they do, they have to pay the king X*Y + Y*Z + Z*X in taxes.
Return -1 if the lord cannot reach his goal. Otherwise, return the smallest total amount of taxes with which the lord can reach his goal.
Notes
- For the chosen constraints the answer always fits into a 64-bit signed integer.
Constraints
- 1 <= A <= B <= N <= 100,000,000.
12 3 3 Returns: 54
One optimal solution is to split the land into two halves (cost 36) and then separately each half into halves (cost 9 twice).
10 3 4 Returns: 33
One optimal solution is to directly split the land into pieces of size 3, 3, and 4.
47 1 47 Returns: 0
Clearly, the optimal solution is to do nothing.
70 40 50 Returns: -1
A land of size 70 cannot be split into pieces of size between 40 and 50, inclusive.
47 4 7 Returns: 945
Submissions are judged against all 191 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LandSplitter with a public method long long cheapest(int N, int A, int B) · 191 test cases · 2 s / 256 MB per case