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.