Concurrently Balanced Strings
플래티넘 I의견: 0
Farmer John's cows are all of a very peculiar breed known for its distinctive appearance -- each cow is marked with a giant spot on its hide in the shape of a parenthesis (depending on the direction the cow is facing, this could look like either a left or a right parenthesis).
One morning, Farmer John arranges his cows into K lines each of N cows (1 <= K <= 10, 1 <= N <= 50,000). The cows are facing rather arbitrary directions, so this lineup can be described by K length-N strings of parentheses S_1,..., S_k. Farmer John notes with great excitement that some ranges of his cows are "concurrently balanced", where a range i...j of cows is concurrently balanced only if each of the strings S_1,..., S_k is balanced in that range.
Given K length-N strings of parentheses, help Farmer John count the number of pairs (i,j) such that the range i...j is concurrently balanced. A string of parentheses is balanced if it has equal numbers of ('s and )'s and every prefix has at least as many ('s as )'s.
Line 1: Two integers, K and N.
Lines 2..K+1: Each line contains a length-N string of parentheses.
A single integer, the number of concurrently balanced ranges.
cbs.incbs.out3 14
)()((())))(())
()(()()()((())
)))(()()))(())3riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Gold
평가 및 의견
Concurrently Balanced Strings
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Concurrently Balanced Strings