Програмчлалын олимпиадын бодлогын архив

Х нь зөв хаалттай илэрхийллүүдийн олонлог байг. Х олонлогийн элементүүд нь зөвхөн '(' ба ')' гэсэн тэмдэгтүүдээс тогтоно. Х олонлогийг дараах байдлаар тодорхойлж болно:

• Хоосон тэмдэгт мөр нь Х-ийн элемент болно
• Хэрэв А нь Х-ийн элемент бол (A) нь Х-ийн элемент байна
• Хэрэв А, В нь Х-ийн элементүүд бол тэдгээрийг залгахад үүсэх АВ нь мөн Х-ийн элемент байна

Доорх илэрхийллүүд нь зөв хаалттай илэрхийллүүд болох ба Х-д харъяалагдана:

()(())()

(()(()))

Харин доорх илэрхийллүүд нь зөв хаалттай илэрхийлэл биш ба Х-д харъяалагдахгүй:

(()))(()

())(()

Е нь зөв хаалттай илэрхийлэл байг (Е нь Х-д харъяалагдана).

Е-гийн урт гэж түүнд орсон тэмдэгтийн тоог хэлнэ.

Е-гийн гүн буюу D(E)-г дараах байдлаар тодорхойлно:

           0                           хэрэв Е нь хоосон тэмдэгт мөр бол

D(E)= D(A)+1           хэрэв А нь Х-д харъяалагддаг ба Е=(A) бол

      max(D(A), D(B)   хэрэв А, В нь Х-д харъяалагддаг ба E=AB бол

Жишээ нь “()(())()”-ийн урт нь 8, гүн нь 2 байна. Эерэг бүхэл n, d тоонууд өгөгдсөн бол n урттай, d гүнтэй зөв хаалттай илэрхийллүүдийн тоо хэд байх вэ?

Оролт

n, d тоонууд зайгаар тусгаарлагдан өгөгдөнө (2<=n<=38, 1<=d<=19).

Гаралт

n урттай, d гүнтэй зөв хаалттай илэрхийллүүдийн тоо болох нэг бүхэл тоог хэвлэнэ.

Жишээ

Оролт:
6 2

Гаралт:
3

Тайлбар: Эдгээр 3 ширхэг зөв хаалттай илэрхийллүүдийг доор жагсаав
(())() 
()(()) 
(()())