Kwadrat magiczny
Limit pamięci: 32 MB
Bajtazar znalazł w swojej piwnicy bardzo stare pudełko.
Gdy je otworzył,
zobaczył wielką stertę tajemniczych tabliczek z wypisanymi na nich liczbami. Oto jedna z nich:
Już po chwili Bajtazar zauważył, że jest to kwadrat magiczny!
Każdy taki kwadrat jest bowiem tabelką rozmiaru , do której wpisano
różnych liczb całkowitych dodatnich
o tej własności, że suma liczb w każdym wierszu, w każdej kolumnie i na każdej
z dwóch przekątnych jest taka sama.
W powyższym kwadracie wszystkie wiersze, kolumny i przekątne sumują się do .
Ucieszony tym odkryciem, Bajtazar zabrał się za przeglądanie innych tabliczek. Niestety na
wielu z nich liczby były zatarte. Po dokładniejszych oględzinach zauważył, że zawsze brakuje
zawartości pewnych pól, z których żadne dwa nie znajdują się w jednym wierszu ani w jednej kolumnie.
Bajtazar uwielbia zagadki matematyczne, ale nie jest dobry w ich rozwiązywaniu.
Czy potrafisz pomóc mu uzupełnić zawartości brakujących pól tak, aby tabliczka znów stanowiła
kwadrat magiczny?
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą rozmiar kwadratu magicznego.
Każdy z kolejnych wierszy zawiera po liczb całkowitych
() pooddzielanych pojedynczymi odstępami;
liczby reprezentują zawartość pierwszego
wiersza tabelki, liczby zawartość drugiego
wiersza itd.
Dodatnie liczby oznaczają zawartość poszczególnych pól
kwadratu magicznego, a zera reprezentują pola, których wartości były zatarte.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy, z których
każdy powinien zawierać dodatnich liczb całkowitych nie większych niż
, pooddzielanych pojedynczymi odstępami.
Liczby te mają reprezentować uzupełniony kwadrat magiczny z wejścia.
Możesz założyć, że dane wejściowe będą tak skonstruowane, że uzupełnienie
tabelki do kwadratu magicznego w opisany sposób będzie możliwe.
Jeśli istnieje więcej niż jedna poprawna odpowiedź, Twój program może
wypisać dowolną z nich.
Przykład
Dla danych wejściowych:
4
0 35 34 4
32 0 7 29
8 30 31 0
33 3 0 36
poprawną odpowiedzią jest:
1 35 34 4
32 6 7 29
8 30 31 5
33 3 2 36
Autorzy zadania: Marian M. Kędzierski, Tomasz Kulczyński.