| II Mistrzostwa Wielkopolski w Programowaniu Zespołowym | 3-4 grudnia 2004 |
|
|
Bartek bardzo lubi bawić się ze swoim starszym bratem Jankiem i z jego kolegami. Oczywiście, jak to zwykle bywa, Bartek psoci się i przeszkadza w zabawach swoim starszym kolegom. Dlatego Janek postanowił założyć klub „Etobicoke guys”, którego członkowie bawią się wyłącznie ze sobą, po to, by móc czasem uwolnić się od przeszkadzającego braciszka. Warunkiem wstąpienia do klubu jest sprostanie pięciu zadaniom, które są bardzo trudne i dokładnie opisane w statucie klubu.
Oto fragment statutu: […] 4.3 Członkiem Klubu może zostać osoba, która potrafi wykonać następujące zadania: 4.3.1 Zjeść kwaśną cytrynkę. 4.3.2 Powiedzieć głośno i wyraźnie „wyindywidualizowaliśmy się z rozentuzjazmowanego tłumu”. 4.3.3 Zbudować latawiec z chusteczki i kilku zapałek. 4.3.4 Wyliczyć ile wynosi 128·11. 4.3.5 Mając N kamyków połączyć każdy z każdym wstążeczką i oznaczyć każdą wstążeczkę liczbą całkowitą dodatnią tak, aby każdy kamyk miał różną sumę liczb na wstążeczkach, które są do niego przymocowane oraz tak, by największe z oznaczeń (tzw. „magiczna liczba”) było jak najmniejsze. Jeśli niemożliwe jest połączenie kamyków wstążeczkami tak, aby spełniony był pierwszy z warunków, należy powiedzieć, że jest to niemożliwe. […] Bartkowi udało się rozwiązać wszystkie zadania oprócz 4.3.5. W Twojej gestii pozostaje pomóc mu przy tym właśnie wyzwaniu.
Dana jest liczba kamyków. Należy określić czy da się ponumerować wstążeczki zgodnie z punktem 4.3.5 statutu. Jeśli tak, to należy również podać jak to zrobić, by „magiczna liczba” była możliwie jak najmniejsza.
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Zestaw składa się z jednej linii, zawierającej liczbę całkowitą N (2 ≤ N ≤ 400), oznaczającą liczbę kamyków, między którymi należy przymocować wstążeczki.
Dla każdego zestawu danych należy wypisać na wyjściu albo jedną linię zawierającą słowo NIE, w przypadku kiedy spełnienie warunku 4.3.5 nie byłoby możliwe, albo N linii, zawierających po N liczb całkowitych, tworzących macierz (tablicę) N×N. W i-tym wierzu i j-tej kolumnie macierzy ma się znajdować wartość oznaczenia wstążeczki, która łączy i-ty kamyk z j-tym. W miejscu oznaczającym połączenie kamyka z samym sobą należy wypisać 0. Jeżeli istnieje kilka rozwiązań, wystarczy podać dowolne z nich.
2 2 3
NIE 0 1 2 1 0 3 2 3 0