Fişierul intrare/ieşire:magic.in, magic.outSursăONI 2009, clasa a 10-a
AutorZoltan SzaboAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/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.1N=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 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 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 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 4N 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 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

  • 3N5
  • 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

magic.inmagic.out
1
3
2 4 6
3 5 1
2
magic.inmagic.out
2
3
2 4 6
3 5 1
111191199911919991

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content