Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1676. Поход
Динамическое программирование и запоминающие функцииБитовые массивы
Олимпиадные задачи на русском языке
| 01/10/2011 | Личное первенство Южного Урала (F) |
| 22/07/2016 | Лето 2016 - 14 (F) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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' (движение на клетку вправо).
Пример ввода
3 3 7 123 322 931
Пример вывода
8 ESES
