Fişierul intrare/ieşire:	dist.in, dist.out	Sursă	Baraj ONI 2007
Autor	Emanuela Cerchez	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.125 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dist

Sa consideram doua propozitii formate din cuvinte scrise cu litere mari ale alfabetului englez, oricare doua cuvinte consecutive fiind separate de unul sau mai multe spatii. Sa consideram c=c₁c₂...c_n si d=d₁d₂...d_m doua cuvinte. Pentru a calcula distanta dintre cuvintele c si d, notata dist(c,d), cuvantul mai scurt se completeaza la sfarsit cu caracterul @ (care are codul ASCII 64), pana se obtin doua cuvinte de aceeasi lungime, apoi se calculeaza suma diferentelor absolute dintre codurile ASCII ale caracterelor situate in cuvintele c si d pe pozitii corespondente:
dist(c,d)=|c₁-d₁|+|c₂-d₂|+...+|c_lg-d_lg|, unde lg=max{n, m}.

Definim distanta dintre doua propozitii ca fiind suma distantelor dintre cuvintele situate in propozitii pe pozitii corespondente. Daca una dintre propozitii are mai putine cuvinte decat cealalta se considera ca la sfarsitul acestei propozitii se afla cuvinte vide (cuvinte de lungime 0), pana la completarea numarului necesar de cuvinte.

De exemplu, sa consideram propozitia P₁="ANA ARE MERE" si propozitia P₂="VASILE NU". Distanta dintre propozitia P₁ si propozitia P₂ este:
dist(P₁,P₂)=dist("ANA", "VASILE")+dist("ARE", "NU")+dist("MERE","").
dist("ANA","VASILE")=|'A'-'V'|+|'N'-'A'|+|'A'-'S'|+|'@'-'I'|+|'@'-'L'|+|'@'-'E'|=
|65-86|+|78-65|+|65-83|+|64-73|+|64-76|+|64-69|=21+13+18+12+9+5=78
dist("ARE","NU")=|'A'-'N'|+|'R'-'U'|+|'E'-'@'|=|65-78|+|82-85|+|69-64|=13+3+5=21
dist("MERE","")=|'M'-'@'|+|'E'-'@'|+|'R'-'@'|+|'E'-'@'|=|77-64|+|69-64|+|82-64|+|69-64|=13+5+18+5=41.
Deci dist(P1,P2)=78+21+41=140

In scopul de a minimiza distanta dintre cele doua propozitii, asupra celei de a doua propozitii putem executa una sau mai multe operatii. O operatie consta in a muta prima litera dintr-un cuvant la sfarsitul cuvantului precedent (daca acesta exista) sau ultima litera dintr-un cuvant la inceputul cuvantului urmator.

Cuvinte vide se pot afla doar la sfarsitul unei propozitii, nu si la inceputul sau in interiorul ei (nici in propozitiile date, nici in propozitiile obtinute in urma aplicarii operatiilor). In momentul in care se efectueaza o mutare asupra unui cuvant de lungime 1 din interiorul propozitiei si acesta devine vid, acesta continua sa existe si mutarile efectuate asupra cuvintelor adiacente nu vor trece peste el. Spre exemplu din propozitia "A", "A", "A" putem ajunge in propozitia "AA", "", "A" si apoi in "AA", "A", "".

Cuvintele din propozitie si cuvintele obtinute in urma operatiilor nu pot sa depaseasca 20 de litere.

Cerinta

Sa se determine distanta minima care se poate obtine intre cele doua propozitii efectuand operatii de tipul celor descrise in enunt. Se cere de asemenea sa se determine si numarul minim de operatii ce trebuie sa fie executate asupra celei de a doua propozitii pentru a obtine distanta minima.

Date de intrare

Fisierul de intrare dist.in contine pe prima linie prima propozitie, iar pe cea de a doua linie a doua propozitie.

Date de iesire

Fisierul de iesire dist.out va contine o singura linie pe care vor fi scrise doua numere naturale separate prin spatiu dmin nrmin, reprezentand in ordine distanta minima dintre cele doua propozitii, respectiv numarul minim de operatii ce trebuie sa fie executate asupra celei de a doua propozitii pentru a obtine distanta minima.

Restrictii

• Lungimea totala a unei propozitii nu depaseste 500 caractere.
• Lungimea maxima a unui cuvant nu depaseste nici in propozitiile date, nici in propozitia obtinuta in urma aplicarii operatiilor din enunt 20 de caractere.
• Numarul maxim de cuvinte dintr-o propozitie este 100.
• Se acorda 60% din punctaj pentru determinarea distantei minime si 100% pentru rezolvarea ambelor cerinte.

Exemplu

Explicatie

Pentru primul exemplu propozitia a doua, dupa aplicarea celor 9 operatii, este:
V ASI LENU

Pentru al doilea exemplu, solutia optima pentru a doua propozitia este AA A.

Cum se trimit solutii?