დროის ლიმიტი: 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 დაკოპირება