Fişierul intrare/ieşire:subsiruri2.in, subsiruri2.outSursăConcursul National Urmasii lui Moisil 2012, Clasa a 10-a
AutorAdrian AirineiAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.4 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsiruri2

Valerică are un şir cu N caractere. Fiind o persoană minimalistă, fiecare caracter din şir poate fi egal cu litera a sau cu litera b. Valerică se întreabă acum în câte moduri poate distribui toate caracterele şirului iniţial astfel încât să rezulte două subşiruri identice. Astfel, notând cu X şi Y două subşiruri care ar rezulta în urma unei distribuţii posibile şi analizând unul câte unul toate caracterele din şirul iniţial, în ordinea în care acestea apar în şir, Valerică va decide, pentru fiecare, dacă îl va introduce la sfârşitul subşirului X sau la sfârşitul subşirului Y. De exemplu, pentru şirul iniţial abab, Valerică poate introduce primul şi al doilea caracter în subşirul X iar al treilea şi al patrulea caracter în subşirul Y, obţinând astfel două subşiruri identice.

Cerinţă

Scrieţi un program care să-l ajute pe Valerică să numere toate posibilităţile distincte de a forma două subşiruri identice din şirul de caractere iniţial.

Date de intrare

Pe prima linie a fişierului subsiruri2.in se află numărul natural N reprezentând numărul de caractere din şirul iniţial. Pe următoarea linie se află şirul format din N caractere din mulţimea {a,b}.

Date de ieşire

Fişierul de ieşire subsiruri2.out va conţine o singură linie pe care va fi scris numărul total de posibilităţi de a forma două subşiruri identice din şirul iniţial.

Restricţii

  • 1 ≤ N ≤ 40, N par
  • pentru 20% din teste N ≤ 16

Exemplu

subsiruri2.insubsiruri2.out
4
abab
2

Explicaţie

Prima posibilitate este să formăm subşirul X din primele două caractere şi subşirul Y din ultimele două caractere. A doua posibilitate este să formăm subşirul X din ultimele două caractere şi subşirul Y din primele două caractere.

subsiruri2.insubsiruri2.out
6
abaaaa
0

Explicaţie

Nu există nicio posibilitate de a forma două subşiruri identice.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content