Să considerăm două propoziţii formate din cuvinte scrise cu litere mari ale alfabetului englez, oricare două cuvinte consecutive fiind separate de unul sau mai multe spaţii.
Să considerăm c=c1c2...cn şi d=d1d2...dm două cuvinte. Pentru a calcula distanţa dintre cuvintele c şi d, notată dist(c,d), cuvântul mai scurt se completează la sfârşit cu caracterul ′@′ (care are codul ASCII 64), până se obţin două cuvinte de aceeaşi lungime, apoi se calculează suma diferenţelor absolute dintre codurile ASCII ale caracterelor situate în cuvintele c şi d pe poziţii corespondente: dist(c,d)=|c1-d1|+|c2-d2|+...+|clg-dlg|, unde lg=max{n, m}).
Definim distanţa dintre două propoziţii ca fiind suma distanţelor dintre cuvintele situate în propoziţii pe poziţii corespondente. Dacă una dintre propoziţii are mai puţine cuvinte decât cealaltă se consideră că la sfârşitul acestei propoziţii se află cuvinte vide (cuvinte de lungime 0), până la completarea numărului necesar de cuvinte.
De exemplu, să considerăm propoziţia P1=″ANA ARE MERE″ şi propoziţia P2=″VASILE NU″. Distanţa dintre propoziţia P1 şi propoziţia P2 este: dist(P1,P2)=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
În scopul de a minimiza distanţa dintre cele două propoziţii, asupra celei de a doua propoziţii putem executa una sau mai multe operaţii. O operaţie constă în a muta prima literă dintr-un cuvânt la sfârşitul cuvântului precedent (dacă acesta există) sau ultima literă dintr-un cuvânt la începutul cuvântului următor. Cuvinte vide se pot afla doar la sfârşitul unei propoziţii, nu şi la începutul sau în interiorul ei (nici în propoziţiile date, nici în propoziţiile obţinute în urma aplicării operaţiilor). Cuvintele din propoziţie şi cuvintele obţinute în urma operaţiilor nu pot să depăşească 20 de litere.
Cerinţă
Să se determine distanţa minimă care se poate obţine între cele două propoziţii efectuând operaţii de tipul celor descrise în enunţ. Se cere de asemenea să se determine şi numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.
Date de intrare
Fişierul de intrare dist.in conţine pe prima linie prima propoziţie, iar pe cea de a doua linie a doua propoziţie.
Date de ieşire
Fişierul de ieşire dist.out va conţine o singură linie pe care vor fi scrise două numere naturale separate prin spaţiu dmin nrmin, reprezentând în ordine distanţa minimă dintre cele două propoziţii, respectiv numărul minim de operaţii ce trebuie să fie executate asupra celei de a doua propoziţii pentru a obţine distanţa minimă.
Restricţii
Lungimea totală a unei propoziţii nu depăşeşte 500 caractere.
Lungimea maximă a unui cuvânt nu depăşeşte nici în propoziţiile date, nici în propoziţia obţinută în urma aplicării operaţiilor din enunţ 20 de caractere.
Numărul maxim de cuvinte dintr-o propoziţie este 100.
Se acordă 60% din punctaj pentru determinarea distanţei minime şi 100% pentru rezolvarea ambelor cerinţe.
Exemple
dist.in
dist.out
Explicaţii
ANA ARE MERE
VASILE NU
62 9
Propoziţia a doua, după aplicarea celor 9 operaţii, este: V ASI LENU