Zadanie

Makarónky

Počet bodov: 270

Merlin má dnes cheat day. A na Nesnězeno práve našiel krabicu \(n \times n\) makaróniek s 50% zľavou!

Merlin ako každý vie, že čím je makarónka sladšia, tým je lepšia. Ale zároveň vie, že i keď má ten cheat day, grind nikdy nespí a tak sa rozhodol, že si makarónky vyberie tak, aby každá makarónka susedila so všetkými menej sladkými.

Poraďte mu, ako si má vybrať čo najlepšie makarónky ale stále neprelomiť grind.

Úloha

Vytvorte mriežku čísel od \(1\) po \(5\) veľkosti \(n \times n\) s čo najväčším súčtom.

Pre každé políčko musí platiť, že (hranovo) susedí s políčkom každej nižšej hodnoty – teda napríklad políčko hodnoty \(3\) musí mať susedov s hodnotami \(1\) a \(2\).

(Rozmyslite si, prečo hodnoty väčšie než \(5\) v mriežke nemôžu byť.)

Vstup a Výstup

V tejto úlohe nedostanete žiadny vstup. Namiesto toho je vašou úlohou u seba na počítači vygenerovať riešenia pre niekoľko fixných \(n\) a tieto riešenia odovzdať. Špecificky nás budú zaujímať vaše riešenia pre \(n \in \{3,5,8,13,21,34,55,89,144\}\)

Riešenie pre každé \(n\) vypíšte ako \(n\) riadkov, každý s \(n\) číslicami (bez medzier). Toto riešenie zapíšte do súboru s názvom {n}.txt. Všetky tieto súbory spolu s vaším zdrojovým kódom zazipujte a tento zip odovzdajte ako riešenie.

Váš zdrojový kód môže byť ľubovoľne pomenovaný.

Bodovanie

Za každý z odovzdaných výstupov môžete získať nanajvýš 30 bodov.

To, koľko bodov dostanete je určené tým, o koľko nižší je súčet vašej mriežky oproti našemu najlepšiemu riešeniu.

Špecificky, ak je váš súčet o \(k\) menší než náš, získate \(30 \cdot 3^{-k/n}\) bodov.

Príklad

Input:

2

Output:

13
12

Input:

4

Output:

1231
3541
2123
3111

Tieto samply sú pre iné \(n\), než máte vy riešiť. Prvý prípad je optimálny, druhý nie.