== include(page="template/taskheader" task_id="magic") ==
Se dă o matrice cu n linii şi n coloane. Coloanele şi liniile sunt etichetate cu numere de la 1 la 2n, folosind fiecare număr câte o singură dată (fig. 1 – exemplu pentru n=3). Vom nota şirul etichetelor asociat liniilor matricei o1,o2,...,on, iar şirul etichetelor asociat coloanelor matricei cu v1,v2,...,vn (fig. 4).
Trebuie să se completeze fiecare element al matricei cu una dintre cifrele 1 sau 9 (fig. 2). Prin concatenarea cifrelor de pe o linie sau o coloană obţinem un număr de n cifre. În total se obţin 2n numere. Aceste numere trebuie să fie distincte două câte două şi aranjându-le în ordinea etichetelor asociate liniilor şi coloanelor trebuie să fie în ordine crescătoare (fig. 3). Vom concatena cele 2n numere în ordinea etichetelor şi obţinem un singur număr de 2n2 cifre. Acest număr îl vom denumi cheie magică. Pentru exemplul din fig. 3 obţinem cheia magică 111191199911919991.
Se dă o matrice cu $N$ linii şi $N$ coloane. Coloanele şi liniile sunt etichetate cu numere de la 1 la $2N$, folosind fiecare număr câte o singură dată (fig.{$1$} – $N$={$3$}). Vom nota şirul etichetelor asociat liniilor matricei o{~1~},o{~2~},...,o{~n~}, iar şirul etichetelor asociat coloanelor matricei cu v{~1~},v{~2~},...,v{~n~} (fig.4).Trebuie să se completeze fiecare element al matricei cu una dintre cifrele $1$ sau $9$ (fig. $2$). Prin concatenarea cifrelor de pe o linie sau o coloană obţinem un număr de $N$ cifre. În total se obţin $2N$ numere. Aceste numere trebuie să fie distincte două câte două şi aranjându-le în ordinea etichetelor asociate liniilor şi coloanelor trebuie să fie în ordine crescătoare (fig. $3$). Vom concatena cele $2N$ numere în ordinea etichetelor şi obţinem un singur număr de {$2$}({$N$}^{$2$}) cifre. Acest număr îl vom denumi cheie magică. Pentru exemplul din fig. $3$ obţinem cheia magică $111191199911919991$.
!problema/magic/?magic.jpg!
h2. Cerinta
Se dau x un număr natural, dimensiunea n a matricei şi cele două şiruri de etichete o1,o2,...,on respectiv v1,v2,...,vn. Să se tipărească numărul de chei magice distincte (dacă x=1) sau cea mai mică cheie magică ce se poate asocia matricei (dacă x=2).
Se dau $x$ un număr natural, dimensiunea $N$ a matricei şi cele două şiruri de etichete o{~1~},o{~2~},...,o{~n~} respectiv v{~1~},v{~2~},...,v{~n~}. Să se tipărească numărul de chei magice distincte (dacă $x$={$1$}) sau cea mai mică cheie magică ce se poate asocia matricei (dacă $x$={$2$}).
h2. Date de intrare
Fişierul de intrare magic.in conţine patru linii. Pe linia 1 se află numărul natural x (1 sau 2). Pe linia 2 se află numărul natural n. Pe linia 3 se află n numere naturale distincte separate prin câte un spaţiu reprezentând şirul o1,o2,...,on iar pe linia 4 – n numere naturale distincte separate prin câte un spaţiu reprezentând şirul v1,v2,...,vn.
Fişierul de intrare $magic.in$ conţine patru linii. Pe linia $1$ se află numărul natural $x$ ({$1$} sau $2$). Pe linia $2$ se află numărul natural $N$. Pe linia $3$ se află n numere naturale distincte separate prin câte un spaţiu reprezentând şirul o{~1~},o{~2~},...,o{~n~} iar pe linia $4$ – $N$ numere naturale distincte separate prin câte un spaţiu reprezentând şirul v{~1~},v{~2~},...,v{~n~}.
h2. Date de ieşire
Fişierul de ieşire magic.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă:
- dacă x=1, numărul cheilor magice distincte;
- dacă x=2, cea mai mică cheie magică.
* dacă $x$={$1$}, numărul cheilor magice distincte;
* dacă $x$={$2$}, cea mai mică cheie magică.
h2. Restricţii
* 3 ≤ N ≤ 5
* $3$ ≤ $N$ ≤ $5$
* Pentru fiecare fişier test există cel puţin o soluţie.
* Pentru 50% dintre teste x=1 (aflarea numărului de chei magice), iar pentru 50% x=2 (aflarea celei mai mici chei magice)
* Pentru 20% dintre teste n=3, 30% dintre teste n=4 şi pentru 50% dintre teste n=5.
* Pentru $50$% dintre teste $x=1$ (aflarea numărului de chei magice), iar pentru $50$% $x=2$ (aflarea celei mai mici chei magice)
* Pentru $20$% dintre teste $N=3$, $30$% dintre teste $N=4$ şi pentru $50$% dintre teste $N=5$.
h2. Exemplu
3
2 4 6
3 5 1
|111191199911919991
|
h3. Explicaţie
Avem două soluţii
1 9 1 1 9 1
9 1 1 9 1 1
9 9 1 9 9 9
Avem două soluţii :
1 9 1 1 9 1
9 1 1 9 1 1
9 9 1 9 9 9
Numerele obţinute în ordinea etichetărilor:
(111, 191, 199, 911, 919, 991) respectiv
(119, 191, 199, 911, 919, 999).
Cele două chei magice sunt 111191199911919991 respectiv 119191199911919999, dintre care prima e mai mică.
* ({$111$}, $191$, $199$, $911$, $919$, $991$)
* ({$119$}, $191$, $199$, $911$, $919$, $999$)
Cele două chei magice sunt $111191199911919991$ respectiv $119191199911919999$, dintre care prima e mai mică.
== include(page="template/taskfooter" task_id="magic") ==
