CSES - Datatähti 2017 loppu - Ruudukko
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Tehtäväsi on muodostaa $n \times n$ -ruudukko, jonka jokaisessa ruudussa on kokonaisluku väliltä $1 \ldots n$. Ruudukon täytyy toteuttaa kaksi vaatimusta:
  1. Jokainen luku $1 \ldots n$ esiintyy ruudukossa tarkalleen $n$ kertaa.
  2. Ruudukon pysty- ja vaakariveistä tulee muodostua $2n$ eri summaa.
Esimerkiksi tapauksessa $5 \times 5$ yksi mahdollinen ruudukko on seuraava:

Jokainen luku $1 \ldots 5$ esiintyy ruudukossa $5$ kertaa, ja rivien summat ovat $[8,11,12,14,15,16,17,18,19,20]$.

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Tulosta jokin ehdot täyttävä ruudukko. Jos mitään ruudukkoa ei ole olemassa, tulosta vain merkkijono "QAQ".

Esimerkki 1

Syöte:
5

Tuloste:
2 3 1 1 1
1 5 5 3 3
2 3 5 2 4
5 4 5 4 1
2 3 4 4 2


Esimerkki 2

Syöte:
2

Tuloste:
QAQ

Osatehtävä 1 (35 pistettä)
  • $2 \le n \le 10$
Osatehtävä 2 (21 pistettä)
  • $2 \le n \le 100$
Osatehtävä 3 (44 pistettä)
  • $2 \le n \le 1000$