O matrice pătratică cu n linii si n coloane cu elementele distincte din mulţimea numerelor naturale {1, 2, ..., n*n}, cu sumele elementelor de pe oricare linie, coloană sau diagonală egale se numeşte pătrat magic.
Următorul algoritm generează un pătrat magic de ordin impar:
- pornim de pe prima linie, coloana din mijloc cu valoarea 1
- numărul natural următor se aşează în matrice avansându-ne pe diagonală (paralel cu diagonala principală) spre stânga-sus, daca avem poziţie liberă în acea direcţie. Când nu mai putem avansa, coborâm cu o linie pe aceeaşi coloană.
Observaţie: avansarea se face în mod ciclic, adică dacă s-a părăsit matricea la stânga, se reintră din dreapta, şi dacă s-a părăsit matricea în partea de sus, se reintră în partea de jos.
Putem genera un pătrat magic de ordin multiplu de 4 conform următorului algoritm:
- Se generează pătratul de dimensiune n în care aşezăm numerele de la 1 la n*n în ordine pe linii.
- Elementele aflate pe linii având număr de ordine pentru care restul împărţirii cu patru este 0 sau 1 şi coloane care nu au această proprietate, sau pe coloane având număr de ordine pentru care restul împărţirii cu patru este 0 sau 1 şi linii care nu au această proprietate, vor fi schimbate cu elementele aflate în poziţii simetrice faţă de mijlocul careului.
Pătratele magice de ordin par, nedivizibil cu 4 le putem genera astfel
- se generează o matrice de litere de ordin m=n/2, completând-o cu literele “L” (primele [m/2]+1 linii), linia următoare cu “U” şi restul liniilor cu “X”, apoi litera “L” din mijlocul careului se interschimbă cu litera “U” aflată sub ea.
- pătratul de dimensiune 2m se construieşte urmărind algoritmul de generare a pătratelor magice impare, considerând pătratul de dimensiune m (m este impar) format din pătratele de dimensiune 2.
- fiecare pătrat de dimensiune 2x2 va avea ca şi corespondent o literă “L”, “U” sau “X” şi va fi completat în ordinea sugerată de această literă:
- aplicăm paşii prezentaţi la pătratul de ordin impar:
Cerinţă
Cunoscând dimensiunea n a unui pătrat magic generat cu unul din algoritmii mai sus, respectiv linia L şi coloana C care determină poziţia unui element, să se calculeze valoarea elementului respectiv.
Date de intrare
Fişierul magic.in conţine pe o linie cele trei numere naturale mai sus menţionate n L C, separate prin spatii.
Date de ieşire
Fişierul magic.out va conţine o singura linie pe care va fi afisat un număr natural, valoarea elementului din pătratul magic de dimensiune n*n , element aflat pe linia L şi coloana C.
