0047. Frere Jacques

Имя входного файла:	jacques.in
Имя выходного файла:	jacques.out
Ограничение по времени:	1 s
Ограничение по памяти:	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 v_i and a constant distance d_i between them. When Jacques starts to cross the highway, the cars on i-th lane are located in all the positions (a_i+m d_i, i) (where a_i 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 v_i. 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: d_i v_i a_i where 1≤ d_i≤ 16, 0≤ v_i≤ d_i, 0≤ a_i≤ d_i-1.

Output file

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

Examples:

jacques.in	jacques.out
15 3 0	4
15 5 2	IMPOSSIBLE

Источник: Petrozavodsk training camp, Summer 2002. Conclusive contest
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение