Nombre de c's amb a abans sense b enmig, i nombre de d's amb a després sense b enmig X17557

L’entrada d’aquest exercici és una seqüència de caràcters sobre {a,b,c,d}. Volem comptar dues coses:

• Volem comptar el nombre de c’s que cumpleixen el següent: abans d’aquesta c hi ha alguna a. A més a més, si considerem la a més propera a aquesta c i anterior a aquesta c, llavors, entre totes dues lletres no hi ha cap b. Per exemple, en el següent mot hem marcat en negreta les c’s que s’han de comptar: cdbdadccbdcacbbdcdabcd.

• Volem comptar el nombre de d’s que cumpleixen el següent: després d’aquesta d hi ha alguna a. A més a més, si considerem la a més propera a aquesta d i posterior a aquesta d, llavors, entre totes dues lletres no hi ha cap b. Per exemple, en el següent mot hem marcat en negreta les d’s que s’han de comptar: cdbdadccbdcacbbdcdabcd.

Entrada

L’entrada és una seqüència de caràcters sobre {a,b,c,d}, en una sola línia.

Sortida

La sortida té dos nombres naturals, en una sola línia, i separats per un espai en blanc:

• el nombre de c’s que tenen una a abans i no hi ha cap b entre totes dues lletres.

• el nombre de d’s que tenen una a després i no hi ha cap b entre totes dues lletres.

Observació

No es pot fer servir cap mètode d’emmagatzemament massiu de dades, ni tan sols string. Llegiu i tracteu l’entrada caràcter a caràcter.

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.