| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 11 | 7 | 4 | 80.000% |
План студенческого городка некоторого университета представляет собой квадрат $n \times n,ドル в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.
В каждом из зданий, включая общежитие и учебный корпус, расположен автомат, торгующий ровно одним продуктом, например, только кофе или только пирожками с мясом. Студенты каждый день ходят из общежития в учебный корпус по переходам, выбирая один из кратчайших путей.
Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата $A_{i,j}$ планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат $A_{i,j}$. Количество таких автоматов на этом пути называется избыточностью автомата $A_{i,j}$. При этом автомат $A_{1,1}$ находится в общежитии, а автомат $A_{n,n}$ --- в учебном корпусе.
Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от 1ドル$ до 2ドルn - 1$ определяет число автоматов с таким значением избыточности.
Первая строка входного файла содержит целое число $n$ (2ドル \leqslant n \leqslant 1500$). Следующие $n$ строк содержат по $n$ чисел в каждой. В $i$-й из этих строк $j$-е число соответствует номеру продукта, продающегося в автомате $A_{i,j}$. Номера продуктов находятся в диапазоне от 1ドル$ до $n^2$.
Выходной файл должен содержать $(2n-1)$ целых чисел --- количество автоматов с избыточностями 1,ドル 2, \ldots, 2n - 1$ соответственно.
Для проверки решений этой задачи используются 50ドル$ тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения $n$ в тестах жюри приведены в следующей таблице.
| Тест | Значение $n$ | Тест | Значение $n$ | Тест | Значение $n$ | Тест | Значение $n$ | Тест | Значение $n$ |
|---|---|---|---|---|---|---|---|---|---|
| 1. | $n = 2 $ | 11. | $n = 50 $ | 21. | $n = 200$ | 31. | $n = 550 $ | 41. | $n = 1050$ |
| 2. | $n = 4 $ | 12. | $n = 60 $ | 22. | $n = 225$ | 32. | $n = 600 $ | 42. | $n = 1100$ |
| 3. | $n = 6 $ | 13. | $n = 70 $ | 23. | $n = 250$ | 33. | $n = 650 $ | 43. | $n = 1150$ |
| 4. | $n = 8 $ | 14. | $n = 80 $ | 24. | $n = 275$ | 34. | $n = 700 $ | 44. | $n = 1200$ |
| 5. | $n = 10$ | 15. | $n = 90 $ | 25. | $n = 300$ | 35. | $n = 750 $ | 45. | $n = 1250$ |
| 6. | $n = 15$ | 16. | $n = 100$ | 26. | $n = 325$ | 36. | $n = 800 $ | 46. | $n = 1300$ |
| 7. | $n = 20$ | 17. | $n = 120$ | 27. | $n = 350$ | 37. | $n = 850 $ | 47. | $n = 1350$ |
| 8. | $n = 25$ | 18. | $n = 140$ | 28. | $n = 400$ | 38. | $n = 900 $ | 48. | $n = 1400$ |
| 9. | $n = 30$ | 19. | $n = 160$ | 29. | $n = 450$ | 39. | $n = 950 $ | 49. | $n = 1450$ |
| 10. | $n = 40$ | 20. | $n = 180$ | 30. | $n = 500$ | 40. | $n = 1000$ | 50. | $n = 1500$ |
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