PatrolRoute
SRM 542 · 2011-11-22 · by ivan_metelsky
Problem Statement
There are exactly X*Y places in the Planar Kingdom: For each pair of integers (x, y) such that 0 <= x < X and 0 <= y < Y there is a place with coordinates (x, y). When a citizen of the kingdom wants to move from (x1, y1) to (x2, y2), the required time is |x1 - x2| + |y1 - y2| (where |t| denotes the absolute value of t).
In order to improve stability in the kingdom, the police wants to introduce a specific patrol route. The route will contain exactly three places A, B, and C. A policeman will visit these three places and verify that everything is as it should be. The three places that determine a valid route must satisfy the following criteria::
- x-coordinates of A, B and C are pairwise distinct.
- y-coordinates of A, B and C are pairwise distinct.
- Let T be the total time required to follow along the route: first from A to B, then from B to C and finally from C back to A. T must be between minT and maxT, inclusive.
You are given the
Constraints
- X and Y will each be between 3 and 4,000, inclusive.
- minT will be between 1 and 20,000, inclusive.
- maxT will be between minT and 20,000, inclusive.
3 3 1 20000 Returns: 6
The time requirement is very flexible in this case. There are 6 patrol routes where both x and y coordinates of places are pairwise distinct.
3 3 4 7 Returns: 0
The time of 7 is too small for any patrol route.
4 6 9 12 Returns: 264
7 5 13 18 Returns: 1212
4000 4000 4000 14000 Returns: 859690013
Don't forget about the modulo!
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PatrolRoute with a public method int countRoutes(int X, int Y, int minT, int maxT) · 119 test cases · 2 s / 256 MB per case