PROBLEMA 9:             SCHERZO
DEADLINE:               Luni, 15 martie 1999
TIMP DE IMPLEMENTARE:   Maxim o ora pentru un elev de a XII-a
DOMENIU:                Programare dinamica
PUNCTAJ:                35 dexteri

O partitura muzicala este scrisa pe V voci, fiecare voce avand cate N note.
Spunem ca un solfegiu SE BRODESTE peste aceasta partitura daca:

1) Solfegiul are tot lungimea de N note si
2) Fiecare din notele solfegiului coincide cu nota de pe pozitia
corespunzatoare a partiturii, pe cel putin una dintre voci.

De exemplu, solfegiul

MI RE LA DO SI FA SOL LA

se brodeste partiturii pe 2 voci cu 6 note:

Vocea I:    MI  RE  DO  DO  SI  FA  FA SI
Vocea II:  SOL  SI  LA  DO SOL  MI SOL LA

Aceasta deoarece notele 1, 2, 5, 6 din solfegiu sunt cantate
conform vocii 1, iar notele 3, 7, 8 sunt cantate pe vocea a doua. Nota
a 4-a (DO) este cantata conform ambelor voci.

(ATENTIE! AUTORUL DETINE DREPTURI EXCLUSIVE ASUPRA SIMFONIEI "MIRELA"
OP. 20. COPIEREA, DIFUZAREA SI INTERPRETAREA IN PUBLIC SUNT STRICT
INTERZISE SI VOR FI PEDEPSITE PE CALE LEGALA)

Spunem ca un solfegiu de o lungime oarecare FALSEAZA in K locuri daca
este nevoie de cel putin K modificari asupra lui pentru a-l face sa se
brodeasca peste partitura. O modificare poate fi:

1) Stergerea unei note din solfegiu
2) Adaugarea unei note in solfegiu
3) Inlocuirea unei note in solfegiu

De exemplu, solfegiul

MI RE SOL DO SI FA SI

falseaza in doua locuri, pentru ca trebuie sa modificam nota SOL in LA
si sa inseram inca un FA intre SI si FA pentru a-l aduce la forma:

MI RE LA DO SI FA FA SI

care se brodeste peste partitura.

Dumneavoastra sunteti profesor la conservator si, la examen, puneti
studentii sa reproduca o partitura in prima auditie, dupa care le
puneti nota in functie de cat de fidela este reproducerea. Natural,
aveti nevoie de un program care sa compare solfegiul (reproducerea) cu
partitura si sa spuna daca solfegiul se brodeste sau in cate locuri
falseaza.

Observatie: In lumea prozaica a calculatoarelor, notele sunt
reprezentate prin numere naturale cuprinse intre 1 si 100.

DATELE DE INTRARE: Fisierul SOLFEGIU.IN contine urmatoarele date:
V N                // Numarul de voci (1<=N<=100) si de note (1<=N<=100)
P11 P12 ... P1N    // Notele primei voci ale partiturii
...                // 1<=Pij<=100
PV1 PV2 ... PVN    // Notele vocii V ale partiturii
M                  // Numarul de note ale solfegiului (1<=M<=100)
S1 S2 ... SM       // Notele solfegiului, 1<=Si<=100

DATELE DE IESIRE: Pe ecran se va tipari unul din mesajele:

Solfegiul se brodeste peste partitura.

sau

Solfegiul falseaza in K locuri.

(unde K este numarul minim de locuri in care solfegiul falseaza).

EXEMPLU: SOLFEGIU.IN
2 8
3 2 1 1 7 4 4 7
5 7 6 1 5 3 5 6
7
3 2 5 1 7 4 7

Raspuns:
Solfegiul falseaza in 2 locuri.

TIMP DE RULARE: O secunda.
COMPLEXITATE RECOMANDATA: O(M*N*V).