Задача №112330. Здоровое питание
В каждом из зданий, включая общежитие и учебный корпус, расположен автомат, торгующий ровно одним продуктом, например, только кофе или только пирожками с мясом. Студенты каждый день ходят из общежития в учебный корпус по переходам, выбирая один из кратчайших путей.
Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата Ai,j планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат Ai,j. Количество таких автоматов на этом пути называется избыточностью автомата Ai,j. При этом автомат A1,1 находится в общежитии, а автомат An,n — в учебном корпусе.
Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от 1 до 2n - 1 определяет число автоматов с таким значением избыточности.
Первая строка входного файла содержит целое число n (2 <= \(n\) <= 1500). Следующие \(n\) строк содержат по \(n\) чисел в каждой. В \(i\)-й из этих строк \(j\)-е число соответствует номеру продукта, продающегося в автомате A i, j. Номера продуктов находятся в диапазоне от 1 до \(n^2\).
Выходной файл должен содержать (2n - 1) целых чисел - количество автоматов с избыточностями 1, 2, ..., 2n - 1 соответственно
Для проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения n в тестах жюри приведены в следующей таблице.
3 1 1 1 2 2 2 3 3 3
0 0 9 0 0
5 1 4 1 3 5 2 1 4 1 2 5 1 1 4 5 3 5 1 1 2 4 3 5 1 1
2 4 9 0 0 1 1 8 0