Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | subsiruri2.in, subsiruri2.out | Sursă | Concursul National Urmasii lui Moisil 2012, Clasa a 10-a |
| Autor | Adrian Airinei | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | subsiruri2.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.in | subsiruri2.out |
|---|---|
| 6 abaaa | 0 |
Explicaţie
Nu există nicio posibilitate de a forma două subşiruri identice.
