Revizia anterioară Revizia următoare
| 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=c1c2...cn si d=d1d2...dm 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)=|c1-d1|+|c2-d2|+...+|clg-dlg|, 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 P1="ANA ARE MERE" si propozitia P2="VASILE NU". Distanta dintre propozitia P1 si propozitia 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
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.
Date de intrare
...
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| dist.in | dist.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
