Nawiasy [B]
Limit pamięci: 64 MB
Poprawnym nawiasowaniem nazywamy taki napis, złożony z nawiasów okrągłych
( i ), w którym jest tyle samo nawiasów otwierających co zamykających
oraz każdy prefiks zawiera co najmniej tyle nawiasów otwierających
co zamykających. Tak więc ()() jest poprawnym nawiasowaniem, lecz
())( nie, gdyż prefiks ()) zwiera więcej nawiasów zamykających niż otwierających.
Spośród dwóch różnych nawiasowań o długości powiemy, że wcześniejsze jest to,
które ma nawias otwierający na pierwszej pozycji, na której nawiasowania te się różnią.
Takie uporządkowanie jest równoznaczne z porządkiem leksykograficznym,
przy założeniu, że .
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia liczby oraz ,
- znajdzie -te w kolejności nawiasowanie spośród wszystkich poprawnych nawiasowań długości
(nawiasowania numerujemy od jedynki),
- wypisze wynik na standardowe wyjście.
Wejście
Wejście zawiera dokładnie dwie liczby naturalne oraz
(, ), oddzielone pojedynczym odstępem.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinno znaleźć się -te w kolejności
nawiasowanie spośród wszystkich poprawnych nawiasowań o długości .
Dane testowe są tak dobrane, że żądane nawiasowanie zawsze istnieje.
Przykład
Dla danych wejściowych:
3 2
poprawną odpowiedzią jest:
(()())
Autor zadania: Krzysztof Dulęba.