Happy subsequences at increasing positions in a matrix X12077
Given a matrix M of n×m characters, a happy subsequence at increasing positions is a triple of positions (i1,j1),(i2,j2),(i3,j3) such that M[i1][j1]=’:’, M[i2][j2]=’-’, M[i3][j3]=’)’ and 0≤i1<i2<i3<n and 0≤j1<j2<j3<m.
Implement a program that reads matrices of characters from the input, and prints the number of happy subsequences at increasing positions in each matrix.
Input
The input has several cases. Each case begins with a line with two positive naturals n,m. Next, there are n lines with m characters each, chosen from {’:’,’-’,’)’}. Consecutive cases are separated by a blank line.
Output
For each case, the program prints in one line the number of happy subsequences at increasing positions in the input matrix.
Observation
Grading up to 10 points:
- Slow solution: 5 points.
- Fast solution: 10 points.
We understand as a fast solution one which is correct, with linear cost and which passes the public and private tests. We understand as slow solution one which is not fast, but it is correct and passes the public tests.
Input
7 4 :-)- -::- )-)- )-:: --)) ::)) )--- 3 10 ::):----:: :))-))):)- -)):))--:: 8 5 ))-:- ):::: ):)): )-::) )::)) -::): ---:: ):-)- 2 8 ))::-)-) )-:)-)-: 8 2 :) :) :- :- ): :) -) )) 2 9 )):)::-)- ::))-):-) 9 10 ))-)--)-:- ))::)-:--) )-)):-)-)- :-))::::)- --)))---:: ::):)::))) -)-:)))-:) :)-::-))): ):-)--)-:- 1 2 -) 7 1 - : : ) ) - : 5 9 ::)::)):- )):):--)- :-))-::-: )-))):-): ::-::-:)) 3 9 ::)):)::- :--)-:)-- ))):)):-: 3 5 ))-:) -:))- :)--) 4 9 )):))::-: -)-)):):- --)---)-) --)::---) 2 5 :::-- ::::: 9 4 :--) ::-: ):): :))- --:) )-:: )--) ::-: )::) 8 9 ))-)):--) )::))):-) ))-):::)- :)-)-:--) ):)-:)):: -:)::))): :::)::::) :)::--))) 9 6 )--::: -):-:- )-::)- --)-:- ))::)- :)))): :----- )::--) :-):): 9 4 )):- -::- :::- )-): :)-- ::-- --)- ---- :-:) 2 3 ):) )-) 2 8 :-)):))) ----::)-
Output
10 4 4 0 0 0 205 0 0 68 9 0 7 0 28 98 33 21 0 0