Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | entanglement.in, entanglement.out | Sursă | Lot Măgurele 2016 - Baraj 6 Seniori |
| Autor | Adrian Budau | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | entanglement.out | Explicatie |
|---|---|---|
| 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}) |
Explicaţie
...
