Problem K
Sprocket Science
The sprockets of the front derailleur are connected to the pedals and drive the rear sprockets by chain. You recall from Sprocket Science $101$ that a cyclist uses derailleurs to select any combination of front and rear sprocket. The resulting gear ratio is $u/v$ where $u$ is the front sprocket sprocket size and $v$ is the rear sprocket size.
You are constrained to exactly two sprockets on the front derailleur and six on the rear derailleur, leading to at most $12$ possible gear ratios. Note that the resulting gear ratios are not necessarily unique.
Input
Twelve lines with two integers $n_i, d_i$ ($1 \le n_i, d_i \le 100$) separated by forward slash, where $n_i/d_i$ is the $i$th gear ratio.
Output
If the specified gear ratios can be achieved, output the required sprocket sizes on two lines with space-separated integers. The first line has the two sprocket sizes for the front derailleur, and the second line gives the six sprocket sizes needed for the rear derailleur. Due to engineering limitations no sprocket size may exceed $10\, 000$. If there are multiple such sets of sprocket sizes that generate the specified gear ratios, output any one of them.
If no solution exists, print impossible.
Sample Input 1 | Sample Output 1 |
---|---|
19/13 10/1 19/14 4/3 20/7 19/7 20/13 19/15 10/7 20/17 19/2 19/17 |
19 20 17 15 14 13 7 2 |
Sample Input 2 | Sample Output 2 |
---|---|
1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/1 1/2 |
impossible |