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{~1~}c{~2~}...c{~n~}$} si {$d=d{~1~}d{~2~}...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{~1~}-d{~1~}|+|c{~2~}-d{~2~}|+...+|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{~1~}="ANA ARE MERE"$} si propozitia {$P{~2~}="VASILE NU"$}. Distanta dintre propozitia $P{~1~}$ si propozitia $P{~2~}$ este:
{$dist(P{~1~},P{~2~})=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 apli�­carii operatiilor). Cuvintele din propozitie si cuvintele obtinute in urma operatiilor nu pot sa depaseasca 20 de litere.

{$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.
 
h2. 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.

h2. Date de intrare

...

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

h2. 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.

h2. 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.

h2. Exemplu
table(example). |_. dist.in |_. dist.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| ANA ARE   MERE
VASILE NU
| 62 9
|
| AA
A A A
| 1 2
|

h3. Explicatie

...

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

== include(page="template/taskfooter" task_id="dist") ==

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

== SmfTopic(topic_id="...") ==

== include(page="template/taskfooter" task_id="dist") ==
 

1844