mugur

Mugur

== include(page="template/taskheader" task_id="mugur") ==

Spunem că un şir $P$ de paranteze rotunde constituie o parantezare corectă dacă $P = {}$ sau $P = M{~1~}M{~2~}..M{~k~}$, adică este format prin concatenarea mugurilor $M{~1~}$, $M{~2~}$, .., $M{~k~}$ $(k ≥ 1)$.

Spunem că un şir $P$ de paranteze rotunde constituie o parantezare corectă dacă $P = Ø$ sau $P = M{~1~}M{~2~}..M{~K~}$, adică este format prin concatenarea mugurilor $M{~1~}$, $M{~2~}$, .., $M{~K~}$ $(K ≥ 1)$.

Spunem că un şir $M$ de paranteze rotunde este un mugure dacă $M = (P)$, adică este format prin încadrarea unei parantezări corecte $P$ între caracterele $($ şi $)$. Astfel, fiind dată o parantezare corectă, se poate spune din câţi muguri este alcătuită. Spre exemplu, parantezarea $S{~1~} = (())()$ are doi muguri: $M{~1~} = (())$ şi $M{~2~} = ()$. şirul $S{~2~} = (()()(()))$ are un singur mugure: $M{~1~} = (()()(()))$.

Spunem că un şir $M$ de paranteze rotunde este un mugure dacă $M = (P)$, adică este format prin încadrarea unei parantezări corecte $P$ între caracterele $($ şi $)$. Astfel, fiind dată o parantezare corectă, se poate spune din câţi muguri este alcătuită. Spre exemplu, parantezarea $S{~1~} = (())()$ are doi muguri: $M{~1~} = (())$ şi $M{~2~} = ()$. Şirul $S{~2~} = (()()(()))$ are un singur mugure: $M{~1~} = (()()(()))$.

h2. Cerinţă

h2. Date de ieşire

În fişierul de ieşire $mugur.out$ va conţine o singură linie cu numărul cerut.

În fişierul de ieşire $mugur.out$ se va găsi numărul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ K ≤ N ≤ 500$

h2. Exemplu

3978