დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 512 მეგაბაიტი
შემავალი მონაცემები: cin
გამომავალი მონაცემები: cout
წყარო: USACO, 2011/12, NOV, BRONZE
ძროხა ბესი გაიქცა და იმალება მაღალი ბალახით დაფარულ გორაკზე. ფერმერმა ჯონმა გადაწყვიტა, რომ შეუმჩნევლად მიეპაროს და ამისათვის აპირებს, რომ ბალახებში ხოხვით მიუახლოვდეს. ბალახები ჯონის თვალწინ ჩანს, როგორც N (1<=N<=50,000) ცალი ფრჩხილისაგან შემდგარი სტრიქონი. მაგალითად ასეთი: )((()())()) ჯონმა იცის, რომ ბესის უკანა ფეხები წააგავს ორ მეზობელ გახსნილ ფრჩხილს ((, ხოლო მისი წინა ფეხები კი - ორ მეზობელ დახურულ ფრჩხილს )). ბესი შეიძლება მდებარეობდეს ნებისმიერ ადგილზე, რომელიც განისაზღვრება, როგორც წინა და უკანა ფეხების წყვილი. გამოთვალეთ ასეთ შესაძლო მდებარეობათა რაოდენობა.
შეტანის ფორმატი:
* სტრიქონი 1: N (1<=N<=50,000) ფრჩხილისაგან შედგენილი სტრიქონი.
გამოტანის ფორმატი:
* სტრიქონი 1: ბესის შესაძლო მდებარეობათა რაოდენობა.
შესატანი მონაცემები
)((()())()) დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება
აქ ბესის შესაძლო მდებარეობათა რაოდენობაა 4.
იხილეთ სურათები ქვემოთ:
| ) | ( | ( | ( | ) | ( | ) | ) | ( | ) | ) | |
| 1 | ^ | ^ | ^ | ^ | |||||||
| 2 | ^ | ^ | ^ | ^ | |||||||
| 3 | ^ | ^ | ^ | ^ | |||||||
| 4 | ^ | ^ | ^ | ^ |