Fişierul intrare/ieşire:entanglement.in, entanglement.outSursăLot Măgurele 2016 - Baraj 6 Seniori
AutorAdrian BudauAdăugată deatatomirTatomir Alex •atatomir
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Entanglement

Fie două şiruri A şi B de lungimi N şi M cu numere naturale mai mici sau egale decât K. Un entanglement al celor două şiruri este o matrice C de dimensiuni N x M unde pentru toate perechile (i,j) valoarea C[i][j] este egală fie cu A[i] fie cu B[j]. 
Dându-se o matrice C, câte perechi de şiruri (A,B) există pentru care C este un entanglement al celor două şiruri?

Cerinţă

Să se scrie un program care, pentru N, M, K şi matricea C cunoscute, determină:

  • dacă matricea C poate fi un entanglement a două şiruri;
  • numărul de perechi de şiruri (A,B) pentru care matricea C reprezintă un entanglement.

Date de intrare

Fişierul de intrare entanglement.in conţine pe prima linie numerele T, N, M şi K, iar pe următoarele N linii câte M numere naturale reprezentând elementele din matricea C.
Dacă T=1 atunci se va stabili dacă matricea C poate fi un entanglement, iar dacă T=2 atunci se va determina numărul de perechi de şiruri (A,B) pentru care C reprezintă un entanglement.

Date de ieşire

Dacă T=1 fişierul de ieşire entanglement.out va conţine cuvântul “DA” dacă C poate fi un entanglement sau cuvântul “NU” în caz contrar.
Dacă T=2 fişierul de ieşire entanglement.out va conţine un singur număr reprezentând restul modulo 1000000007 al numărului de perechi de şiruri pentru care matricea C reprezintă un entanglement.

Restricţii

  • 1 ≤ N, M ≤ 300
  • 1 ≤ K ≤ N * M
  • Pentru teste în valoare de 32 de puncte T = 1.
  • Pentru teste în valoare de 32 de puncte T = 2 şi N, M <= 60.
  • Pentru restul testelor, în valoare de 36 de puncte, T = 2.

Exemplu

entanglement.inentanglement.outExplicatie
1 2 2 2
1 1
1 2
DA
O posibilă soluţie este A = {1, 1} şi B = {1, 2}.
2 2 2 2
1 1
1 2
5
Cele 5 soluţii sunt:
(A = {1, 1}, B = {1, 2})
(A = {1, 1}, B = {2, 2})
(A = {1, 2}, B = {1, 1})
(A = {2, 2}, B = {1, 1})
(A = {1, 2}, B = {1, 2})
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?