Задачи / Статистика /

Номер задачи - 24

Задача Лягушка

Ограничение 3 сек. на тест

Лягушка оказалась в болоте, помогите ей спастись по листкам, которые держатся на плаву 2 секунды и потом исчезают на время Li для i-го листа. Требуется найти время, за которое лягушка сможет доскакать до указанного листа. Лягушка не может прыгать на исчезающий лист. За одну секунду лягушка прыгает только на один ближайший лист. Листы, находящиеся по диагонали тоже считаются соседними.

Входные данные:

N – количество листьев, далее на каждой строчке дано описание i-го листа: x y t, где x y – положение листа, t – период его исчезания. Лягушка должна добраться от первого листа до последнего, если она не может добраться туда за минимальное время, которое надо найти и она утонет или это невозможно – то вывести "no solution". Листы появляются через t секунд после начала, кроме первого. Все значения – целые числа.

Выходные данные:

Время необходимое лягушке, либо “no solution”.

Пример