Clock
Time limit2sMemory limit256 MB
Given a visible arc of the clock face and optional known hand positions, count how many valid hand configurations match the constraints.
- Level
Medium6 of 10
- Topics
- Implementation, Math, Brute force, Simulation
- Solved
- No attempts yet
Problem
A client, apparently a private detective, brought a clock in terrible condition to a clock repair shop. Not only has it stopped, but someone also spilled paint on it, so not the whole face is visible. The client asked you to determine what time the clock stopped at. Since the face is not fully visible, you and the client agreed to determine the number of possible positions of the hands that the clock could have had when it stopped.
The face is a circle marked with minute divisions from 0 to 59 in steps of one. The clock has only an hour hand and a minute hand. At every moment each hand lies exactly on some division. Each hour corresponds to 5 divisions. From minute 0 through minute 11 inclusive the hour hand is on the first division of the hour, from 12 through 23 on the second, from 24 through 35 on the third, from 36 through 47 on the fourth, and from 48 through 59 on the fifth. For example, if the time is 3:30, the minute hand is on division 30 and the hour hand is on division 17.
On the clock you were given, because of the spilled paint, only part of the face inside some sector is visible. Determine the number of distinct positions of the hands that the clock could have had when it stopped.
The picture shows the queries from the example.
Input
The first line contains the number of queries q (1 ≤ q ≤ 1000). The next q lines contain the queries, one per line.
Each query is given by four integers a, b, h, and m separated by spaces (0 ≤ a, b ≤ 59), which describe the range of visible values. This means that only the part of the face that the minute hand passes from minute a to minute b, inclusive, is visible. In particular, if a ≤ b, the segment [a; b] is visible, and if b < a, the segment [a; 59] ∪ [0; b] is visible.
h describes the position of the hour hand. If h = −1, the hour hand is not visible. Otherwise h lies in the segment from a to b described above. m describes the position of the minute hand in the same way.
Output
For each query, print a single integer on a separate line: the number of positions of the hands that the clock could have had at the moment it stopped.