eolymp
bolt
Try our new interface for solving problems
Məsələlər

Стрекоза и муравей 2

Стрекоза и муравей 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Сложные и многогранные взаимоотношения между стрекозой и муравьем отражены отнюдь не только в известной басне Крылова. В частности, согласно одноименной грузинской народной сказке, стрекоза выручает муравья, попавшего в реку до того, как тот успел научиться плавать. Кстати, о том как обстоят дела у муравья в этом смысле в данный момент, народный эпос пока умалчивает. Рассказ о том, как все же стрекоза сумела выручить муравья из беды, заслуживает отдельной задачи. Мы же проследим за событиями с того момента, когда спасенный муравей решил пригласить своего спасителя в лучшую хинкальную леса, в котором они обитали. В момент, когда муравью пришла в голову такая мысль, друзья находились на краю опушки, которую можно представить как прямоугольный участок размером M×N. Каждая клетка этого участка характеризуется своей высотой от уровня моря. При этом, друзья находятся в клетке (1, 1), а вожделенная хинкальная расположена на другом конце опушки в клетке (M, N). Каждым очередным шагом друзья могут попасть в любую из соседних клеток, расположенных внутри опушки. Две квадратные клетки считаются соседними, если у них есть общая сторона.

Перед друзьями стала задача подобрать такой маршрут, чтобы возможно меньше устать. Для стрекозы предпочтителен маршрут, проходящий по меньшему количеству клеток, а для муравья – маршрут, в котором минимальна максимальная высота, на которую ему придется подняться. Начальная и конечная клетки входят в маршрут. Так как по версии грузинской народной сказки и стрекоза, и муравей хорошо воспитаны, то каждый из них настаивает на варианте, объективно предпочтительном для друга. Но учитывая, что это муравей пригласил стрекозу, а не наоборот, он настоял, чтобы был избран маршрут, наиболее удобный для стрекозы. В случае существования нескольких таких маршрутов будет выбран тот из них, который устраивает муравья как можно больше.

Giriş verilənləri

Первая строка содержит значения чисел M и N. Каждая из следующих M строк содержит по N чисел. j-е число i+1–ой строки соответствует высоте клетки (i, j). M и N – целые числа, причем 2M, N500. Высота каждой клетки – это целое число, принадлежащее диапазону 1..1000000000 включительно.

Çıxış verilənləri

Единственная строка с парой целых чисел – длина и максимальная высота выбранного друзьями маршрута, соответственно.

Müəllif Николоз Джимшелеишвили
Mənbə Зимняя школа, Харьков 2009, контест Теодора Заркуа и его учеников