Description

This is an integer problem. The wheels do not rotate by non-integer angles like $1.5$ degrees or $23.51234123$ degrees. For example, a wheel might rotate at $20$ degrees per second, or even $30$–$40$ degrees per second if it is fast.

All angles $\theta$ in this problem are restricted to $0 \le \theta \le 359$ degrees. After a wheel rotates through $359$ degrees, the next degree is $0$. Each wheel has a fixed rotational speed $\omega$ in seconds, with $1\le \omega\le 180$.

The starting angle of each slot and the slot size (or width) are both integers, measured in degrees. On a single wheel, there is at least one degree between any two slots. The width includes both the starting and ending angles of the slot, i.e., 0 179 covers $[0,179]$, totaling $180$ angles.

At the starting position (time $0$), all the starting marks on the wheels are aligned along a straight line. Your program must compute the earliest time when a slot on each wheel aligns with slots on all the other wheels (i.e., a beam of light can pass through five slots, one on each of the five wheels), at any angle.

Input Format

There are five lines in the input, one per wheel.

The first number is the wheel’s rotational speed $\omega$. The next number is the number of slots $n$, where $1 \le n \le 5$. The following $n$ pairs $(\theta_i,\varphi_i)$ give the starting angle and width of each slot.

Output Format

Output a single line with one integer, the earliest time when light can pass through all five wheels. If there is no solution, output none.

30 1 0 120
50 1 150 90
60 1 60 90
70 1 180 180
90 1 180 60

9

Hint

Sample explanation:

After $9$ seconds, the five sets of slots are $[270^\circ,30^\circ]$, $[240^\circ,330^\circ]$, $[240^\circ,330^\circ]$, $[90^\circ,270^\circ]$, $[270^\circ,330^\circ]$, so a beam can enter from $270^\circ$.

Translation from NOCOW.

USACO Training Section 3.2.

Translated by ChatGPT 5