Входной файл: Attr.in Выходной файл: Attr.out Время на тест: 5 секунд Автор задачи: А.Н. Данченко Тесты к задаче:Скачать
В Ламерлэнде на главной площади открылся новый центр развлечений. Он представляет собой ромбовидное помещение, разбитое на 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-ом уровне. Компьютерная помощь, ремонт компьютера, абонентское обслуживание. . Юридический центр "Лидер ликвидация фирм санкт петербург.
