Входной файл: Attr.in Выходной файл:
Attr.out Время на тест: 5 секунд Автор задачи:
А.Н. Данченко Авторское решение:Pascal Тесты к
задаче:Скачать
В Ламерлэнде на главной площади открылся новый
центр развлечений. Он представляет собой ромбовидное помещение,
разбитое на K*K одинаковых комнат, в которых находятся аттракционы.
Комнаты также имеют ромбовидную форму. Посетитель на каждом уровне,
а их всего N (N=K*2-1), может посетить только одну комнату. Входом
является комната на первом уровне, а выходом - комната на последнем.
Переходить из комнаты в комнату можно, только если они имеют общую
стену. Для того, чтобы привлечь большее число посетителей, в каждой
комнате посетитель получает сувенир. Всего бывает M типов сувениров.
Билл приехал специально для того, чтобы посетить
новый центр. У него есть список комнат (назовем их "интересными").
Билл хочет посетить как можно больше таких комнат. Также у Билла
есть много друзей, и он собирается привезти им сувениры. Однако в
Ламерлэнде принято друзьям дарить одинаковые подарки, поэтому Билл
хочет собрать как можно больше сувениров одного типа.
Пример
Рис 1.
Рис 2.
На рисунке 1 показан центр развлечений, состоящий
из пяти уровней. Числа внутри комнат обозначают номер уровня, на
котором находится комната. На рисунке 2 показан центр,
соответствующий примеру входных данных. Серым фоном выделены
"интересные" комнаты. Число в каждой комнате показывает тип
сувенира, который посетитель получает во время посещения этой
комнаты.
Ваша задача - помочь Биллу. Требуется найти
маршруты, при которых он посетит максимальное количество
"интересных" комнат, и из этих маршрутов выбрать тот, при котором
Билл соберет максимальное количество сувениров какого-либо одного
типа.
Формат ввода
В первой строке входного файла Attr.in находятся N
- количество уровней и M - количество различных типов сувениров.
Затем в каждой из N следующих строк описывается очередной уровень. В
каждой такой строке находятся числа Tij, описывающие
комнату с номером j, находящуюся на i-ом уровне (комнаты на каждом
уровне нумеруются слева направо, начиная с единицы). Tij
- положительное, если комната является "интересной", отрицательное в
ином случае. Модуль этого числа обозначает тип сувенира в данной
комнате.
Ограничения
Все числа на вводе - целые. 2 < N < 200
- нечетное. 0 < M < 101. 1 <= | Tij |
<= M .
Формат вывода
В первой строке выходного файла Attr.out должны
находится два числа, разделенные пробелом. Первое - количество
посещенных "интересных" комнат, второе - максимальное количество
сувениров одного типа при этом маршруте. Затем в последующих N
строках должны быть числа по одному в строке. Число в (i+1)-ой
строке обозначает номер комнаты, посещенной на i-ом уровне.
