Diferente pentru problema/lant intre reviziile #8 si #41

Diferente intre titluri:

lant
Lant

Diferente intre continut:

Ion este un lingvist pasionat. Recent el a descoperit un text scris intr-o limba necunoscuta. Textul este scris pe mai multe linii si este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spatii sau/si semne de punctuatie $(,:;.!?-)$.
Ion a fost frapat ca exista multe similitudini intre cuvintele din text. Fiind foarte riguros, Ion defineste similitudinea a doua cuvinte dupa cum urmeaza.
Fie $c1$ si $c2$ doua cuvinte. Cuvantul $c1$ poate fi obtinut din cuvantul $c2$ printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:
Fie $c$~1~ si $c$~2~ doua cuvinte. Cuvantul $c$~1~ poate fi obtinut din cuvantul $c$~2~ printr-o succesiune de operatii elementare. Operatiile elementare ce pot fi folosite sunt:
| Operatia
| Efect
| Exemplu
|_. Operatia
|_. Efect
|_. Exemplu
|
| $move(c1,c2)$
| Muta primul caracter din $c1$ la sfarsitul cuvantului $c2$
| Daca $c1="alba"$ si $c2="neagra"$, dupa efectuarea operatiei $move(c1, c2)$, $c1$ va fi $"lba"$, iar $c2$ va fi $"neagraa"$.
| {$move(c$}~1~{$,c$}~2~{$)$}
| Muta primul caracter din $c$~1~ la sfarsitul cuvantului $c$~2~
| Daca $c$~1~{$="alba"$} si $c$~2~{$="neagra"$}, dupa efectuarea operatiei{$move(c$}~1~{$,c$}~2~{$)$}, $c$~1~ va fi $"lba"$, iar $c$~2~ va fi $"neagraa"$.
|
| $insert(c1,x)$
| Insereaza caracterul $x$ la inceputul lui $c1$
| Daca $c1="alba"$ si $x='b'$, dupa executarea operatiei $insert(c1,x)$, $c1$ va fi $"balba"$.
| {$insert(c$}~1~{$,x)$}
| Insereaza caracterul $x$ la inceputul lui $c$~1~
| Daca $c$~1~{$="alba"$} si $x='b'$, dupa executarea operatiei {$insert(c$}~1~{$,x)$}, $c$~1~ va fi $"balba"$.
|
| $delete(c1)$
| Sterge primul caracter din $c1$
| Daca $c1="alba"$, dupa executarea operatiei $delete(c1)$, $c1$ va fi $"lba"$.
| {$delete(c$}~1~$)$
| Sterge primul caracter din $c$~1~
| Daca $c$~1~{$="alba"$}, dupa executarea operatiei {$delete(c$}~1~$)$, $c$~1~ va fi $"lba"$.
|
Definim similitudinea dintre $c1$ si $c2$ ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c1$ in cuvantul $c2$ (operatiile $move$ nu se numara).
Fie $c0$ primul cuvant din text. Incepand cu $c0$ putem construi lanturi de $k-similitudine$.
Definim similitudinea dintre $c$~1~ si $c$~2~ ca fiind numarul minim de operatii $insert$ si $delete$ ce trebuie sa fie executate pentru a transforma cuvantul $c$~1~ in cuvantul $c$~2~ (operatiile $move$ nu se numara).
Fie $c$~0~ primul cuvant din text. Incepand cu $c$~0~ putem construi lanturi de $k-similitudine$.
Un lant de $k-similitudine$ este o succesiune de cuvinte distincte din text cu urmatoarele proprietati:
* daca cuvantul $x$ apare in lant inaintea cuvantului $y$, atunci prima aparitie a lui $x$ in text preceda prima aparitie a lui $y$ in text;
* daca $x$ si $y$ sunt cuvinte consecutive in lant (in ordinea $x$ $y$) , atunci similitudinea dintre $x$ si $y$ este $≤ k$;
* daca $x$ si $y$ sunt cuvinte consecutive in lant (in ordinea $x$ $y$) , atunci similitudinea dintre $x$ si $y$ este mai mica sau egala cu $k$;
* lantul este maximal (adica nu putem adauga inca un cuvant la sfarsitul acestui lant, astfel incat sa fie respectate proprietatile precedente).
h2. Cerinta
 
Scrieti un program care sa determine numarul de lanturi de $k-similitudine$ care incep cu $c$~0~.
 
h2. Date de intrare
...
Fisierul de intrare $lant.in$ contine pe prima linie valoarea $k$. Pe urmatoarele linii se afla textul dat.
h2. Date de iesire
...
Fisierul de iesire $lant.out$ va contine o singura linie pe care va fi scris numarul de lanturi de $k-similitudine$ care incep cu $c$~0~.
h2. Restrictii
* $... ≤ ... ≤ ...$
* Lungimea unei linii din text nu depaseste $1000$ de caractere.
* Lungimea unui cuvant nu depaseste $30$ de caractere.
* Numarul total de cuvinte distincte $≤ 150$.
* Pentru datele de test, numarul de lanturi de $k-similitudine$ care incep cu $c$~0~ va fi $≤2000000000$ (doua miliarde).
h2. Exemplu
table(example). |_. lant.in |_. lant.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5
ana are mere, banane,
pere si castane.
| 6
|
h3. Explicatie
...
Lanturile de $5-similitudine$ care se pot forma sunt:
$ana are mere pere$
$ana are pere$
$ana are banane castane$
$ana are si$
$ana banane castane$
$ana si$
== include(page="template/taskfooter" task_id="lant") ==
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2063