Fişierul intrare/ieşire:tst.in, tst.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorPatrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.175 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tractor sau tractoras?

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.

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.

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.

Date de intrare

Fişierul de intrare tst.in va contine un sir de caractere format numai din litere mici ale alfabetului englez, de lungime N.

Date de ieşire

În fişierul de ieşire tst.out se va afisa un singur numar, anume numarul cerut.

Restricţii

  • 1 ≤ N ≤ 5000
  • Voi nu faceti for-ul niciodata asa pentru ca nu sunteti smecheri!

Exemplu

tst.intst.out
baa
13

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?