Matrix

matrix

==Include(page="template/taskheader" task_id="matrix")==

== include(page="template/taskheader" task_id="matrix") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| matrix.in | matrix.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="matrix") ==

==Include(page="template/raw")==
 
matrix
 
 
 
Cercetatorii din tara lui Papura-Voda au descoperit harta genomului uman si au reprezantat-o ca matrice de dimensiuni MxM ce contine litere mici ale alfabetului englez. O specie extrateresta a atacat umanitatea, utilizand un virus a carui definitie a fost identificata, de aceeasi bravi cercetatori, sub forma unei matrici de dimensiuni NxN care contine tot litere mici ale alfabetului englez. Cercetatorii vor sa afle gradul de infestare a genomului uman, care se masoara in numarul de aparitii a definitiei virusului in harta acestuia. Problema este insa ceva mai complicata, deoarece virusul se poate deghiza interschimband de oricate ori, oricare doua pozitii din matricea care il defineste.
 
h2. Cerinta
 
 
 
Determinati numarul de aparitii (incluzandu-le si pe cele deghizate) ale definitiei virusului in harta genomului uman.
 
h2. Date de Intrare
 
 
 
Prima linie contine doua numere, M si N, cu semnificatia de mai sus. Urmeaza M linii continand cate M caractere (fara spatii) reprezentand harta genomului uman. Urmatoarele N linii contin N caractere (fara spatii) reprezentand definitia virusului
 
h2. Date de Iesire
 
 
 
Fisierul de iesire va contine pe prima linie numarul de aparitii ale virusului (eventual deghizat) in harta genomului uman.
 
h2. Restrictii si precizari
 
 
 
o 1 <= N <= M <= 1000
o Ambele matrici contin litere mici ale alfabetului englez
o Doua aparitii diferite ale virusului se pot suprapune partial (vezi exemplul)
o Pentru 50% din teste M <= 200
o Nu stiu daca se poate identifica un virus analizand harta genomului uman. Povestea e pura fictiune. Orice asemanare cu realitatea este intamplatoare si neintentionata.
 
h2. Exemplu
 
 
 
 
|matrix.in |matrix.out |
 
|3 2 |4 |
| | |
|acb | |
| | |
|bda | |
| | |
|acb | |
| | |
|ab | |
| | |
|cd | |
 
 
 
==Include(page="template/taskfooter" task_id="matrix")==