Simulation - Lot 2014 Baraj 3 Juniori | partitie

Se consideră un număr natural $N$ și fie $A$ mulţimea tuturor numerelor naturale cuprinse între $1$ şi $N^2$.

Numim partiție a mulțimii $A$ un set de submulțimi $A_1, A_2, ..., A_N$ cu proprietățile:

• Reuniunea celor $N$ submulțimi are ca rezultat mulțimea $A$;
• Intersecția oricăror două submulțimi distincte este mulțimea vidă;
• Numărul de elemente ale fiecărei submulțimi $A_i$, $1 \leq i \leq N$, este $N$;
• Elementele fiecărei submulţimi sunt aşezate în ordine crescătoare;

Cerinţă

Să se scrie un program care determină o partiție a mulțimii $A$ cu proprietăţile:

• Sumele elementelor fiecărei submulţimi $A_i$, $1 \leq i \leq N$, sunt egale;
• Pentru oricare submulțime $A_i$, $1 \leq i \leq N$, diferența oricăror două elemente succesive ale sale este diferită de $N + 1$ și de $N - 1$;

Date de intrare

Fişierul de intrare partitie.in conţine pe prima linie numărul natural $N$, cu semnificaţia de mai sus.

Date de ieșire

Fişierul de ieşire partitie.out va conţine $N$ linii. Pe linia $i$ vor fi scrise elementele submulţimii $A_i$, $1 \leq i \leq N$, separate prin câte un spaţiu.

Restricții și precizări

• $5 \leq N \leq 1 \ 000$;

Exemplu

partitie.in

5

partitie.out

1 8 15 17 24
3 10 12 19 21
5 7 14 16 23
2 9 11 18 25
4 6 13 20 22

Explicație

$N = 5$;
$A = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25\}$
$A_1 = \{1,8,15,17,24 \}$; $1+8+15+17+24 = 65$
$A_2 = \{3,10,12,19,21 \}$; $3+10+12+19+21= 65$
$A_3 = \{5,7,14,16,23 \}$; $5+7+14+16+23 = 65$
$A_4 = \{2,9,11,18,25 \}$; $2+9+11+18+25 = 65$
$A_5 = \{4,6,13,20,22 \}$; $4+6+13+20+22 = 65$

Pentru toate submulțimile $A_i$, $1 \leq i \leq 5$ diferența oricăror două elemente succesive nu este $4$ sau $6$