Fişierul intrare/ieşire:chei.in, chei.outSursăAlgoritmiada 2019 Runda PreONI
AutorMihai CalanceaAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test0.3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Chei

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 (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.

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.

Date de intrare

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.

Date de ieşire

În fişierul de ieşire chei.out se afla numarul de perechi de chei pe care nu le pot distinge.

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

Exemplu

chei.inchei.out
abaa
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?