4004 - Nerdson and Alejandra

Created by V Copa UPR - Manuel Alejandro Diaz Perez
Added by Kino (2018-05-23)
Limits
Total Time: 15000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Nerdson has a small daughter named Alejandra, and he wants the first word that she says to be "papa", so he often repeats "papa" to achieve his goal. Finally one day he heard that his daughter say something similar to what was waiting, the problem is that adults are not smart enough to understand the language "Gorgogeo", so Nerdson needs a program that analyzes the gorgo-word and tell how many times the string "papa" appears as a sub-sequence.
Nerdson tiene una hija pequeña llamada Alejandra, y quiere que la primera palabra que diga  sea "papa", por lo que muy a menudo le repite "papa" para lograr su objetivo. Finalmente un dia escuchó que su hija gorgogeó algo parecido a lo que estaba esperando, el problema es que los adultos no son lo suficientemente inteligentes para entender el idioma “Gorgogeo”, por lo que Nerdson necesita un programa que analice la gorgo-palabra y le diga cuántas veces aparece la cadena "papa" como subsecuencia.
;jsessionid=4D23FFC19137958318711DD5448FDABE
Nerdson has a small daughter named Alejandra, and he wants the first word that she says to be "papa", so he often repeats "papa" to achieve his goal. Finally one day he heard that his daughter say something similar to what was waiting, the problem is that adults are not smart enough to understand the language "Gorgogeo", so Nerdson needs a program that analyzes the gorgo-word and tell how many times the string "papa" appears as a sub-sequence.

Input specification

The first line contains an integer N (N <= 10000), the number of characters in the gorgo-word. The second line contains a gorgo-word of N characters. A gorgo-word is composed only of lowercase letters of the English alphabet.
La primera línea contiene un entero N (N <= 10000), la cantidad de caracteres de la gorgo-palabra.
La segunda línea contiene una gorgo-palabra de N caracteres.
Una gorgo-palabra esta compuesta solo por letras minúsculas del alfabeto inglés.
The first line contains an integer N (N <= 10000), the number of characters in the gorgo-word. The second line contains a gorgo-word of N characters. A gorgo-word is composed only of lowercase letters of the English alphabet.

Output specification

A line with an integer representing the number of times the string "papa" appears as a sub-sequence in the gorgo-word.
Una línea con un entero representando la cantidad de veces que aparece la cadena “papa” como subsecuencia en la gorgo-palabra.
The first line contains an integer N (N <= 10000), the number of characters in the gorgo-word. The second line contains a gorgo-word of N characters. A gorgo-word is composed only of lowercase letters of the English alphabet.

Sample input

6
papapa

Sample output

5

Hint(s)