Fişierul intrare/ieşire:mugur.in, mugur.outSursăCCEX 2009
AutorLucian BocaAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.4 secLimită de memorie8290 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mugur

Spunem că un şir P de paranteze rotunde constituie o parantezare corectă dacă P = Ø sau P = M1M2..MK, adică este format prin concatenarea mugurilor M1, M2, .., MK (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 S1 = (())() are doi muguri: M1 = (()) şi M2 = (). Şirul S2 = (()()(())) are un singur mugure: M1 = (()()(())).

Cerinţă

Fiind curios din fire, Amadaeus se întreabă câte parantezări corecte cu K muguri poate alcătui cu N perechi de paranteze. Deoarece rezultatul poate fi un număr foarte mare, Amadaeus se mulţumeşte (de aceasta dată) cu restul acestui număr la împărţirea cu 123457.

Date de intrare

Fişierul de intrare mugur.in conţine o singură linie cu numerele N şi K.

Date de ieşire

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

Restricţii

  • 1 ≤ K ≤ N ≤ 500

Exemplu

mugur.inmugur.out
4 2
5

Explicaţie

Avem şirurile:

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content