Antysymetria
Limit pamięci: 32 MB
Bajtazar studiuje różne napisy złożone z zer i jedynek.
Niech będzie takim napisem, przez będziemy oznaczać odwrócony (czyli "czytany wspak") napis ,
a przez będziemy oznaczać napis powstały z przez zamianę wszystkich zer na jedynki, a jedynek na zera.
Bajtazara interesuje antysymetria, natomiast niezbyt lubi wszystko co symetryczne.
Antysymetria nie jest tylko prostym zaprzeczeniem symetrii.
Powiemy, że (niepusty) napis jest antysymetryczny, jeżeli dla każdej pozycji w ,
-ty znak od końca jest różny od -tego znaku, licząc od początku.
W szczególności, niepusty napis złożony z zer i jedynek jest antysymetryczny wtedy i tylko wtedy,
gdy .
Na przykład, napisy 00001111 i 010101 są antysymetryczne, natomiast 1001 nie jest.
W zadanym napisie złożonym z zer i jedynek chcielibyśmy wyznaczyć liczbę jego spójnych (tj. jednokawałkowych)
niepustych fragmentów, które są antysymetryczne.
Jeżeli różne fragmenty odpowiadają takim samym słowom, to i tak należy je policzyć wielokrotnie.
Wejście
Pierwszy wiersz standardowego wejścia zawiera liczbę (), oznaczającą długość napisu.
Drugi wiersz zawiera napis złożony z liter 0 i/lub 1 o długości .
Napis ten nie zawiera żadnych odstępów.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną
liczbę całkowitą, oznaczającą liczbę spójnych fragmentów wczytanego napisu,
które są antysymetryczne.
Przykład
Dla danych wejściowych:
8
11001011
poprawną odpowiedzią jest:
7
Antysymetryczne fragmenty to: 01 (pojawia się dwukrotnie),
10 (także dwukrotnie), 0101, 1100 oraz 001011.
Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.