W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Wyrażeniem nawiasowym nazwiemy niepusty ciąg składający się z nawiasów otwierających i zamykających. Powiemy, że wyrażenie nawiasowe jest poprawne, jeżeli każdy nawias otwierający można sparować z nawiasem zamykającym, występującym po nim, tak aby ciąg nawiasów znajdujących się pomiędzy nimi również był poprawnym ciągiem nawiasowym.
Na przykład (()())() jest poprawnym wyrażeniem nawiasowym, ale )( i ()( już poprawne nie są.
Bajtazar w swojej pracy naukowej skorzystał z programu wypisującego pewne poprawne wyrażenie nawiasowe , mające kluczowe znaczenie dla jego badań. Niestety, słowo to zaginęło w gąszczu innych nawiasów, które przez przypadek mogły być wypisane zarówno przed nim, jak i po nim. Bajtazar otrzymał więc słowo nawiasowe, które zawiera w sobie jako spójny fragment szukane słowo , jednak nie wie, gdzie się ono zaczyna i gdzie kończy.
Zrozpaczony, poprosił Ciebie o pomoc w wyznaczeniu wszystkich możliwych położeń poprawnych słów nawiasowych w otrzymanym słowie. Ma bowiem nadzieję, że jest ich niewiele ...
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą długość słowa, które odczytał Bajtazar. W drugim wierszu znajduje się nawiasów (bez odstępów) - jest to odczytane słowo nawiasowe.
Możesz założyć, że w testach wartych przynajmniej punktów zachodzi dodatkowy warunek .
Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą oznaczającą liczbę fragmentów odczytanego słowa, które są poprawnymi słowami nawiasowymi.
Dla danych wejściowych:
10 )(())()(()
poprawną odpowiedzią jest:
5Autor zadania: Michał Włodarczyk.