Nosaukums
Iekavu izteiksme (iekavas2)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
64%

Definīcija

X ir mazākā kopa, kas definēta sekojoši:

  • tukšā virkne pieder kopai X,
  • ja A, B pieder kopai X, tad gan (A), gan AB pieder kopai X.

Kopas X elementus sauc par korekti veidotām iekavu izteiksmēm.
Sekojošas virknes ir korekti veidotas iekavu izteiksmes:

()(())()
(()(()))


Sekojošas izteiksmes nav korekti veidotas iekavu izteiksmes:

(()))(()
())(()


Pieņemsim, ka E ir korekti veidota iekavu izteiksme.
Virknes E garums ir tajā esošo iekavu skaits.
Virknes E dziļums D(E) tiek definēts sekojoši:

      { 0                ja E ir tukša
D(E)= { D(A)+1           ja E = (A), un A pieder X
      { max(D(A),D(B))   ja E = AB, un A, B pieder X


Uzrakstiet programmu, kas dotām naturālu skaitļu n un d vērtībām nosaka, cik ir korekti veidotas iekavu izteiksmes garumā n un dziļumā d!


Ievaddatu raksturojums

Ievaddatu vienīgā rinda satur divu naturālu skaitļu n un d vērtības, kas atdalītas ar tukšumsimbolu, 2 <= n <= 38, 1 <= d <= 19.


Izvaddatu raksturojums

Izvaddatu vienīgajai rindai jāsatur viena vesela skaitļa vērtība - korekti veidoto iekavu izteiksmju garumā n un dziļumā d skaits. 


Piezīmes

Ir tieši trīs korekti veidotas izteiksmes garumā 6 un dziļumā 2:

(())()
()(())
(()())

 
Uzdevums izmantots 5.Baltijas informātikas olimpiādē Rīgā 1999.gadā.


Paraugdati

Stdin
6 2
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.