24/04/2024 02:03:02

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1676. Поход

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Пете нужно подготовить маршрут для похода. У Пети есть карта, на которой для каждого участка местности указана сложность его преодоления. Во время похода можно двигаться только на юг или на восток, переходя с одного участка местности на другой. Петя хочет найти маршрут, сложность которого как можно ближе к заданной сложности `с`. Если есть два маршрута со сложностью `c-d` и `c+d`, то предпочтительнее маршрут меньшей сложности. Из двух маршрутов одинаковой сложности можно выбрать любой.

Первая строка ввода содержит три целых числа – размеры местности `n` и `m` (`2\ ≤\ n,\ m\ ≤\ 100`) и требуемая сложность похода `c` (`0\ ≤\ c\ ≤\ 1000`). Далее следует `n` строк, содержащих по `m` символов – цифры от '0' до '9'. Цифра означает сложность преодоления соответствующего участка местности. Начальная точка маршрута находится верхнем левом углу карты, а конечная – в правом нижнем углу.

Вывести в первой строке сложность найденного маршрута. Во второй строке вывести маршрут как последовательность из `(n+m-2)` букв 'S' (движение на клетку вниз) и 'E' (движение на клетку вправо).

Пример ввода

Пример вывода

8
ESES

01/10/2011	Личное первенство Южного Урала (F)
22/07/2016	Лето 2016 - 14 (F)