- 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.