მრგვალი ფრჩხილები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: BALTOI, 1999


ვთქვათ, X არის მრგვალი ფრჩხილებისაგან კორექტულად შედგენილი გამოსახულება. Xის ელემენტებს წარმოადგენენ მხოლოდ ’(’ და ’)’ 
სიმბოლოები. X კრებული ასე განისაზღვრება:
ცარიელი სტრიქონი ეკუთვნის X-ს.
თუ A ეკუთვნის X-ს, მაშინ (A) ეკუთვნის X-ს.
თუ A და B ეკუთვნიან X-ს, მაშინ კონკატენაცია AB ეკუთვნის X-ს.
მაგალითად, შემდეგი სტრიქონები წარმოადგენენ მრგვალი ფრჩხილებისაგან კორექტულად ფორმირებულ გამოსახულებებს (და ამის გამო
ეკუთვნიან X კრებულს):
() (()) () 
(() (())) 
შემდეგი სტრიქონები წარმოადგენენ მრგვალი ფრჩხილებისაგან არაკორექტულად ფორმირებულ გამოსახულებებს (და ამის გამო არ ეკუთვნიან 
X კრებულს):
 (()))
(()  ()) (() 

ვთქვათ, E არის მრგვალი ფრჩხილებისაგან კორექტულად შედგენილი გამოსახულება (შესაბამისად ეკუთვნის X კრებულს). E-ს სიგრძე ვუწოდოთ მასში შემავალი მრგვალი ფრჩხილების საერთო რაოდენობას. E-ს სიღრმე D(E) განისაზღვრება შემდეგნაირად: D(E)=0, თუ E ცარიელია. D(E)=D(A)+1, თუ E=(A) და A ეკუთვნის X-ს. D(E)=max(D(A),D(B)), თუ E=AB და A და B ეკუთვნიან X-ს. მაგალითად გამოსახულება “() (()) ()”-ის სიგრძეა 8, ხოლო სიღრმე – 2.  n სიგრძისა და d სიღრმის მქონე რამდენი კორექტული გამოსახულება შეიძლება აიგოს მრგვალი ფრჩხილებისაგან მოცემული მთელი დადებითი n და d რიცხვებისათვის?

 დაწერეთ პროგრამა, რომელიც: წაიკითხავს ორ მთელ n და d რიცხვს; გამოთვლის კორექტულად ფორმირებულ n სიგრძისა და d სიღრმის ყველა შესაძლო გამოსახულების რაოდენობას;

შემავალი მონაცემები: ერთადერთ სტრიქონი შეიცავს ჰარით გაყოფილ ორ მთელ n და d რიცხვს (2<n<38 და 1<d<19). 

გამომავალი მონაცემები:  ერთადერთი სტრიქონი უნდა შეიცავდეს ერთ მთელ რიცხვს – კორექტულად ფორმირებულ n სიგრძისა და d სიღრმის ყველა შესაძლო გამოსახულების რაოდენობას.

მაგალითი

შემავალი მონაცემები:  6 2    

გამომავალი მონაცემები:  3     

სულ არსებობს 6 სიგრძისა და 2 სიღრმის მქონე გამოსახულების 3 ვარიანტი: (()) ()           () (())             (() ())




მაგალითები

შესატანი მონაცემები
6 2 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება