0047. Frere Jacques

Input file name: jacques.in
Output file name: jacques.out
Time limit: 1 s
Memory limit: 64 megabytes

There is a very busy one-directional highway with k lanes. Jacques wants to walk from one its side to another. But – what a problem – there are too many cars…

The cars within each lane have a constant speed vi and a constant distance di between them. When Jacques starts to cross the highway, the cars on i-th lane are located in all the positions (ai+m di, i) (where ai is given for each lane) for any integer m. Jacques starts from point (0, 0).

In our model Jacques and all the cars move in turn. The first move is Jacques'. Jacques may remain on the current lane, walk one lane forward or walk one lane backward (of course he may return to his starting position when he is on the first lane). If his y-coordinate becomes equal to k+1 he is considered a winner. Jacques can't change his x-coordinate which is always equal to 0.

Then the cars move. All they increase their x coordinates by vi. If any car goes through the position where Jacques stands, Jacques is considered dead (the positions where this car was before the move or after it are also included).

Then Jacques (if left alive) moves again.

Your task is to calculate the minimal number of moves require for Jacques to reach the other side of highway or to determine that it is impossible.

Input file

The first line of the input file contains one integer number k (1≤ k≤ 13). The next k lines contain three numbers each: di vi ai where 1≤ di≤ 16, 0≤ vi≤ di, 0≤ ai≤ di-1.

Output file

Output the minimal number of moves for Jacques. If it is impossible to walk over the highway, write one string "IMPOSSIBLE".


15 3 04

Source: Petrozavodsk training camp, Summer 2002. Conclusive contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution

Printable version