ClassRankings
SRM 774 · 2020-01-09 · by lg5293
Problem Statement
There are three schools, numbered 0, 1, and 2.
You are given three
The number of students in school i is equal to amt[i]. Students from the same school are indistiguishable.
All these students took part in a national exam. Each student earned a distinct integer number of points on the exam. In addition, you know that each student from school i earned between lo[i] and hi[i] points, inclusive.
After the exam, we will order the students by increasing number of points, and write down which school each student came from. This will give us a string of length sum(amt) consisting of '0's, '1's, and '2's.
Count the number of distinct strings that can result from a valid scenario, modulo 10^9+7. Note that in some test cases (such as the one shown in Example 1) there can be no valid scenarios at all.
Constraints
- amt, lo, hi will contain exactly 3 elements.
- Each element of amt will be between 1 and 50, inclusive.
- Each element of lo, hi will be between 1 and 1,000, inclusive.
- For each valid i, lo[i] will be less than or equal to hi[i].
{1,1,1}
{1,1,1}
{100,100,100}
Returns: 6
We can get the strings 012, 021, 102, 120, 201, 210.
{1,1,1}
{1,1,1}
{1,1,1}
Returns: 0
There is no way for the students to finish with distinct scores.
{2,1,3}
{5,1,2}
{6,1,4}
Returns: 1
{2,4,3}
{1,4,8}
{6,10,12}
Returns: 15
{50,50,50}
{1,1,1}
{150,150,150}
Returns: 824706821
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ClassRankings with a public method int countWays(vector<int> amt, vector<int> lo, vector<int> hi) · 81 test cases · 2 s / 256 MB per case