Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_18_05 - Poprawne nawiasowanie |
Pewnego dnia w magicznym świecie matematycznych wyrażeń, bohaterowie, Alicja, Borys i Zosia, postanowili stworzyć wyjątkowe wyrażenie algebraiczne. Zaczęli od dodawania, odejmowania, mnożenia i dzielenia, aż wreszcie doszli do nawiasów.
Alicja była mistrzynią w układaniu nawiasów, więc postanowiła stworzyć najbardziej intrygujące wyrażenie. Zaczęła od nawiasu otwierającego "(" i dodała do niego nawias zamykający ")". Borys dołączył się, dodając kolejny zestaw nawiasów "()". Zosia, która była mistrzynią w wyznaczaniu spójnych podciągów, postanowiła policzyć, ile różnych poprawnych nawiasowań można utworzyć.
Pierwszym razem Alicja i Borys stworzyli wyrażenie (), a Zosia stwierdziła, że jest to jedno spójne nawiasowanie. Następnie dodali jeszcze jeden zestaw nawiasów, tworząc ()(). Tym razem Zosia dostrzegła trzy spójne nawiasowania - (),() i ()(). Każdy kolejny zestaw nawiasów dodawany przez bohaterów dostarczał Zosi nowych możliwości do policzenia spójnych podciągów.
Alicja, Borys i Zosia pracowali wspólnie, dodając coraz więcej nawiasów, tworząc bardziej skomplikowane wyrażenia. Zosia liczyła spójne nawiasowania, a ich liczba rosła eksponencjalnie. Każdy kolejny nawias dodawany przez bohaterów dawał im nową przygodę w świecie matematycznych kombinacji.
Pod koniec dnia, gdy wyrażenie przybrało formę ()()()..., Zosia podsumowała swoje odkrycia. Okazało się, że liczba spójnych podciągów tego magicznego wyrażenia była równa liczbie możliwych nawiasowań, jakie stworzyli razem Alicja, Borys i Zosia. I takie jest zadanie dla Ciebie!
Wejście
W pierwszym i jedynym wierszu n par nawiasów (0 < n ≤ 106) postaci ().
Wyjście
Jedna liczba określająca liczbę podciągów reprezentujących poprawne nawiasowanie.
Przykład
Wejście:
()()()
Wyjście:
6
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2023-12-30 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |