FairSplit
SRM 775 · 2020-01-15 · by misof
Problem Statement
Vegard and Bard have some packs of sweets: for each i between A and B, inclusive, they have one pack that contains i sweets. The pair (A, B) is called fair if Vegard and Bard can divide the packs among themselves in such a way that each of them gets the same total number of sweets.
Count all fair pairs (A, B) such that A <= B, loA <= A <= hiA, and loB <= B <= hiB.
Constraints
- 1 <= loA <= hiA <= 2,000,000,000.
- 1 <= loB <= hiB <= 2,000,000,000.
7 7 1 15 Returns: 3
A must be 7, and B must be between 1 and 15, inclusive. There are three fair pairs that match these constraints: (7,10), (7,13), and (7,14). In the first case, Vegard can take 7+10 sweets. In the second case, Vegard can take 10+12+13 sweets. In the third case, Vegard can take 7+10+12+13 sweets. We can easily verify that in each of those cases Bard will get the same number of sweets as Vegard.
101 200 1 100 Returns: 0
For these constraints we cannot have A <= B, so there is no fair pair that matches these constraints.
1 4 5 10 Returns: 11
4 17 12 33 Returns: 129
1 2000000000 1 2000000000 Returns: 999970186260287400
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FairSplit with a public method long long count(int loA, int hiA, int loB, int hiB) · 107 test cases · 2 s / 256 MB per case