== include(page="template/taskheader" task_id="magic") ==
Poveste şi cerinţă...
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 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$ ...
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
În fişierul de ieşire $magic.out$ ...
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ă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $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$.
h2. Exemplu
table(example). |_. magic.in |_. magic.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3
2 4 6
3 5 1
| 2
|
table(example). |_. magic.in |_. magic.out |
|2
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
Numerele obţinute în ordinea etichetărilor:
* ({$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") ==
