06/04/2025 20:12:58

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

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

Задачи

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

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

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

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

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

Задачи

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)