5. Obytná štvrť

Kráľovstvo Slnka a Paliem sa rozhodlo, že postaví mesto uprostred púšte. Obytná štvrť bude pozostávať z \(n\times n\) domov usporiadaných do štvorca. Každá budova bude mať nejaký počet podlaží a všetky podlažia budú rovnako vysoké.

Na prízemí každého domu bude bývať služobníctvo a na poschodiach vyššia šľachta. Interiér budovy je však pre vyššiu šľachtu nepostačujúci, stiesnené priestory veru nie sú nič pre nich. Aby si mohli užívať čerstvý vzduch, chceli by mať šľachtici možnosť prejsť sa po streche vedľajšej budovy. Na to však musí vedľa stáť budova so strechou v správnej výške. Napríklad vedľa každej štvorpodlažnej budovy musí byť jednopodlažná, dvojpodlažná aj trojpodlažná budova.

Kráľ by chcel, aby celkový počet podlaží v obytnej štvrti bol čo najväčší a preto vyhlásil súťaž o najlepší územný plán.

Úloha

Vašou úlohou je pre dané \(n\) vytvoriť plán mesta. Plán mesta je matica \(n\times n\) čísel predstavujúcich výšky budov. Každé číslo musí susediť so všetkými menšími kladnými celými číslami, ako je ono samé. Keďže číslo má najviac štyroch susedov, tak najväčšie možné číslo v matici je 5.

Počet bodov, ktoré za úlohu dostanete bude závisieť od celkového súčtu čísel v matici.

Odovzdávanie príkladu

V tejto úlohe namiesto toho, aby ste odovzdali program, odovzdávate hotové plány mesta. Zaujímajú nás plány mesta pre nasledovné \(n\): 3, 5, 8, 13, 21, 34, 55, 89 a 144.

Pre každé takéto \(n\) vyrobte jeden súbor, ktorý má presne \(n\) riadkov a v každom riadku presne \(n\) cifier (za ktorými nasleduje znak konca riadku, čiže \n). Cifry vyjadrujú počet podlaží veže. Tento súbor nazvite n.txt, teda napríklad 13.txt pre \(n=13\). Následne tieto súbory všetky zabaľte do jedného zipu a odovzdajte.

Okrem toho odovzdajte stručný popis toho, ako ste úlohu riešili.

Hodnotenie

Každý z 9 odovzdaných plánov sa hodnotí samostatne a za každý môžete získať \(0\) až \(\frac{4}{3}\) bodu. Keď váš odovzdaný plán má celkovo o \(d\) podlaží menej ako náš, dostanete \({4}\cdot{3^{-1-d/n}}\) bodov.

Napríklad, ak pre \(n=3\) odovzdáte plán s \(20\) podlažiami, dostanete plný počet, približne \(1.333\) bodu. Ak odovzdáte plán s \(17\) podlažiami, dostanete \(0.444\) bodu a za plán s \(19\) podlažiami približne \(0.924\) bodu.

Za popis môžete dostať 0 až 3 body. Nemusíte písať dlhé eseje, stačí stručne popísať, ako ste úlohu riešili, alebo ako by ste ju chceli riešiť.

Príklady

Input:

2

Output:

11
23

Input:

6

Output:

112111
234521
111321
112311
121311
111211

Prvý ukážkový vstup má optimálny počet podlaží, druhý sa dá ešte dosť zlepšiť.