== include(page="template/taskheader" task_id="tst") ==
Poveste şi cerinţă...
Inca din timpuri indepartate, notiunea de "smecherie" era cunoscuta, dar tinuta ascunsa pentru a nu afla toti "dusmanii". Smecheria este un concept abstract, de la a fi saltat de mascati, pana la a pica la judet chiar daca ai iesit primul. Desigur, daca vreti sa aprofundati acest subiect, $Dani & Nicolae$ va stau permanent la dispozitie. Probabil va intrebati de ce v-am vorbit despre acest fenomen. In randul tinerilor din ziua de astazi, majoritatea dintre ei prefera sa isi denumeasca numele functiilor sau varibilelor intr-un mod original pentru a se simti... smecheri.
== code(cpp) |
S = 0;
cin>>sir;
for (int i=0;i<strlen(sir);++i) {
for (int j=i;j<strlen(sir);++j) {
S += Smecherie (i, j) ;
}
}
cout<<S;
==
Vestea buna este ca am aflat prin smecherie ca functia $Smecherie(i,j)$ returneaza numarul de secvente distincte de pe intervalul $(i,j)$. Vestea proasta e ca nu stim daca problema aceasta este penala sau doar o simpla tractoreala.
h2. Cerinta
Avand un sir de caractere de lungime $N$, trebuie sa calculati cate secvente sunt distincte pe fiecare interval al sirului si sa afisati suma acestor numere.
h2. Date de intrare
Fişierul de intrare $tst.in$ ...
Fişierul de intrare $tst.in$ va contine un sir de caractere **format numai din litere mici ale alfabetului englez**, de lungime $N$.
h2. Date de ieşire
În fişierul de ieşire $tst.out$ ...
În fişierul de ieşire $tst.out$ se va afisa un singur numar, anume numarul cerut.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 5000$
* Voi nu faceti for-ul niciodata asa pentru ca nu sunteti smecheri!
h2. Exemplu
table(example). |_. tst.in |_. tst.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| baa
| 13
|
h3. Explicaţie
...
Smecherie (0,0) = 1 => b
Smecherie (0,1) = 3 => b, a, ba
Smecherie (0,2) = 5 => b, ba, baa, a, aa
Smecherie (1,1) = 1 => a
Smecherie (1,2) = 2 => a, aa
Smecherie (2,2) = 1 => a
1 + 3 + 5 + 1 + 2 + 1 = 13
== include(page="template/taskfooter" task_id="tst") ==
