Fişierul intrare/ieşire:domenii.in, domenii.outSursăFMI No Stress 10
AutorStefan DascalescuAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Domenii

Vazand potentialul sirurilor de caractere, zeii BFR-isti au realizat peste ce comoara au putut sa dea. Dar fiindca suntem la FMI No Stress si vacanta de iarna se apropie, ei s-au gandit sa fie blanzi cu voi astazi. Astazi, v-au dat cadou un sir de caractere de lungime n care contine litere mici si caracterul "." (punctul) si vor de la voi sa aflati numarul de subsiruri de tip domeniu ale acestui sir de caractere.

Un subsir de tip domeniu este un subsir de tipul .litera1litera2, unde litera1 si litera2 sunt diferite. Chiar daca un domeniu apare de mai multe ori ca subsir, il vom numara de cate ori apare. Practic, trebuie numarate numarul de triplete de forma (i, j, k) astfel incat i < j < k, s[i] = '.', iar s[j] si s[k] sunt litere diferite.

Date de intrare

Fişierul de intrare domenii.in contine pe prima linie numarul n, lungimea sirului de caractere. Pe urmatoarea linie avem sirul de caractere s de lungime n.

Date de ieşire

În fişierul de ieşire domenii.out se va afla pe prima linie numarul de subsiruri de tip domeniu al sirului de caractere.

Restricţii

  • 1 ≤ n ≤ 10^6
  • Pentru 20% din teste, 1 ≤ n ≤ 200
  • Pentru alte 20% din teste, 1 ≤ n ≤ 2000
  • Sirul poate contine doar caracterul "." (punct) sau litere mici ale alfabetului englezesc.

Exemplu

domenii.indomenii.out
7
.p.zior
16

Explicaţie

Domeniile valide sunt .pz, .pi, .po, .pr, .zi, .zo, .zr, .zi, .zo, .zr, .io, .ir, .io, .ir, .or, .or . Dupa cum am spus, un domeniu e numarat de cate ori apare, chiar daca in acest exemplu avem doua aparitii ale lui .ir, le vom numara pe amandoua.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?