== include(page="template/taskheader" task_id="subsiruri2") ==
Poveste şi cerinţă...
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.
h2. 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.
h2. Date de intrare
Fişierul de intrare $subsiruri2.in$ ...
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}$.
h2. Date de ieşire
În fişierul de ieşire $subsiruri2.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 40$, $N$ par
* pentru $20%$ din teste $N ≤ 16$
h2. Exemplu
table(example). |_. subsiruri2.in |_. subsiruri2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
abab
| 2
|
h3. 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.
table(example). |_. subsiruri2.in |_. subsiruri2.out |
| 6
abaaaa
| 0
|
h3. Explicaţie
...
Nu există nicio posibilitate de a forma două subşiruri identice.
== include(page="template/taskfooter" task_id="subsiruri2") ==
== include(page="template/taskfooter" task_id="subsiruri2") ==
