# 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 **v _{i}** and a
constant distance

**d**between them. When Jacques starts to cross the highway, the cars on

_{i}**i**-th lane are located in all the positions

**(a**(where

_{i}+m d_{i}, i)**a**is given for each lane) for any integer

_{i}**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 |

*Source: Petrozavodsk training camp, Summer 2002. Conclusive contest*

*Author: Andrew Lopatin, Nick Durov*

Discuss Submit a solution

Printable version