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ă
Cerinţă
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).
Date de intrare
Fişierul de intrare magic2.in conţine patru linii. Pe prima linie se află numărul natural x (1 sau 2). Pe a doua linie se află numărul natural n. Pe a treia linie se află n numere naturale distincte separate prin câte un spaţiu reprezentând şirul o1,o2,...,on iar pe linia a patra n numere naturale distincte separate prin câte un spaţiu reprezentând şirul v1,v2,...,vn.
Date de ieşire
Fişierul de ieşire magic2.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ă.
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.
Exemple
magic2.in
magic2.out
Explicaţii
1
3
2 4 6
3 5 1
2
Avem două soluţii 1 9 1
9 1 1
9 9 1
1 9 1
9 1 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ă.
