Fişierul intrare/ieşire:	magic.in, magic.out	Sursă	ONI 2009, clasa a 10-a
Autor	Zoltan Szabo	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.025 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 – N=3). Vom nota şirul etichetelor asociat liniilor matricei o₁,o₂,...,o_n, iar şirul etichetelor asociat coloanelor matricei cu v₁,v₂,...,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.

Cerinta

Se dau x un număr natural, dimensiunea N a matricei şi cele două şiruri de etichete o₁,o₂,...,o_n respectiv v₁,v₂,...,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).

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 o₁,o₂,...,o_n iar pe linia 4 – N numere naturale distincte separate prin câte un spaţiu reprezentând şirul v₁,v₂,...,v_n.

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ă.

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.

Exemplu

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ă.

Cum se trimit solutii?