Subseqüències felices a posicions creixents en una matriu X12077
Donada una matriu M de n×m caràcters, una subseqüència feliç a posicions creixents és una tripleta de posicions (i1,j1),(i2,j2),(i3,j3) tal que M[i1][j1]=’:’, M[i2][j2]=’-’, M[i3][j3]=’)’ i 0≤i1<i2<i3<n i 0≤j1<j2<j3<m.
Implementeu un programa que llegeix matrius de caràcters d’entrada, i escriu el nombre de subseqüències felices a posicions creixents en cada matriu.
Entrada
L’entrada té varis casos. Cada cas comença amb una línia amb dos naturals positius n,m. Després venen n línies amb m caràcters cadascuna, escollits d’entre {’:’,’-’,’)’}. Dos casos consecutius estan separats per una línia en blanc.
Sortida
Per a cada cas, el programa escriu el nombre de subseqüències felices a posicions creixents de la matriu d’entrada en una línia.
Observació
Avaluació sobre 10 punts:
- Solució lenta: 5 punts.
- solució ràpida: 10 punts.
Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.
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