== include(page="template/taskheader" task_id="chei") ==
Poveste şi cerinţă...
Ai mai multe chei pe un inel. Unele sunt rotunde (codificate cu caracterul 'a'), altele sunt patrate (codificate cu caracterul 'b'), ..., altele sunt in forma de 'hashtag':problema/hashtag (codificate cu caracterul 'z'). În rest, cheile nu au nimic pe ele care să le distingă, iar asta e o problemă. Uneori problema asta poate fi atenuată de dispunerea cheilor pe inel.
Spre exemplu, daca pe inel sunt exact cheile "abaa".
Putem spune ceva de genul: "Ok, pai aia de la apartament e singura patratica, cea de la garaj e cea rotunda care nu e adiacenta cu cea patratica, iar cu celelalte doua rotunde e cam nasol, va trebui tot timpul sa le incerc pe ambele worst-case (atunci cand vreau sa deschid apartamentul lui Sorin sau beciul lui Sorin, de exemplu).
Deoarece cheile se misca in buzunar, inelul se poate roti circular sau poate fi intors pe dos.
h2. Cerinta
Se da un sir de caractere care descrie felul in care arata la o instanta oarecare dispunerea cheilor pe inel. Sa se numere cate perechi de chei au proprietatea ca nu le pot distinge nici in urma unei analize a dispunerii celorlalte chei.
h2. Date de intrare
Fişierul de intrare $chei.in$ ...
Fişierul de intrare $chei.in$ contine, pe prima linie, un sir de caractere. El contine doar litere mici ale alfabetului englez si se termina cu caracterul '\n', semnficand sfarsitul de linie. Fiecare caracter corespunde unui tip de cheie, in functie de forma ei.
h2. Date de ieşire
În fişierul de ieşire $chei.out$ ...
În fişierul de ieşire $chei.out$ se afla numarul de perechi de chei pe care nu le pot distinge.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$, unde $N$ este numarul de chei.
* Pentru $22%$ din punctaj, $N ≤ 100$
* Pentru $35%$ din punctaj, $N ≤ 2.000$
* Pentru $51%$ din punctaj, $N ≤ 4.000$
h2. Exemplu
table(example). |_. chei.in |_. chei.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| abaa
| 1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="chei") ==
