Subsecuencias felices en posiciones crecientes de una matriz X12077
Dada una matriz M de n×m caracteres, una subsecuencia feliz a posiciones crecientes es una tripleta de posiciones (i1,j1),(i2,j2),(i3,j3) tal que M[i1][j1]=’:’, M[i2][j2]=’-’, M[i3][j3]=’)’ y 0≤i1<i2<i3<n y 0≤j1<j2<j3<m.
Implementad un programa que lee matrices de caracteres de entrada, y escribe el número de subsecuencias felices a posiciones crecientes en cada matriz.
Entrada
La entrada tiene varios casos. Cada caso comienza con una linea con dos naturales positivos n,m. Después vienen n lineas con m caracteres cada una, escogidos de entre {’:’,’-’,’)’}. Casos consecutivos están separados por una linea en blanco.
Salida
Para cada caso, el programa escribe en una linea el número de subsecuencias felices a posiciones crecientes de la matriz de entrada.
Observación
Evaluación sobre 10 puntos:
- Solución lenta: 5 puntos.
- Solución rápida: 10 puntos.
Entendemos como solución rápida una que es correcta, de coste lineal y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.
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