Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PA07_NAW - Nawiasy

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 2n 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 '(' < ')'.

Napisz program, który znajdzie k-te w kolejności nawiasowanie spośród wszystkich poprawnych nawiasowań długości 2n (nawiasowania numerujemy od jedynki).

Wejście

Wejście zawiera dokładnie dwie liczby naturalne n oraz k (1 ≤ n ≤ 4000, 1 ≤ k ≤ 1018), oddzielone pojedynczym odstępem.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinno znaleźć się k-te w kolejności nawiasowanie spośród wszystkich poprawnych nawiasowań o długości 2n. Dane testowe są tak dobrane, że żądane nawiasowanie zawsze istnieje.

Przykład

Wejście:

3 2

Wyjście:

(()())


Dodane przez:Rafal Nowak
Data dodania:2007-04-20
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:ASM32-GCC ASM32 C CSHARP C++ 4.3.2 CPP CPP14 C99 PAS-GPC PAS-FPC
Pochodzenie:Potyczki Algorytmiczne 2007 (kwiecień)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.