Baltic Olympiad in Informatics: 2013 Day 2, Problem 3
Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using
the letter e
. Victor is a big fan of Ernest and tries to imitate him in writing a novel, but is looking
for a real challenge. He uses only the first ten characters of the alphabet (namely abcdefghij
).
Ironically, the e
key on his computer breaks halfway through the novel, and for consistency, he
decides to delete all the e
s he has already written. His friend, a programmer, recommended him to
use the text editor Vim to perform this task. Unfortunately, Victor is not very familiar with Vim, and
knows only three different commands: x
, h
and f
.
x
deletes the character at the cursor. The cursor position (counted from the left) does not change. Victor shall not use this command if the cursor is at the last character of the document.h
moves the cursor one step backward (to the left). Nothing happens if the cursor is at the beginning of the document.f
waits for the user to input another character, and then moves the cursor forward to the next occurrence of
(even if the character at the cursor happens to be
). Nothing happens if
does not occur anywhere to the right of the cursor position.
For example, if the current text is
where the cursor is denoted by a frame , then
x
would give jeffe
hadabigidea
h
would give jeff
ehadabigidea
fi
would give jeffehadabi
gidea
Write a program that calculates the least number of key presses that Victor needs to use to delete
all the e
s in the document, but no other letters. Initially, the cursor is at the first character of the
document. Note that the e
key is broken, so the command fe
cannot be used.
Input
The first line contains the integer , the length of the document. The next line contains
characters,
each one of the ten lowercase letters from
a
to j
. The first and the last letter of the input are both
different from e
.
Output
The only line of output should contain exactly one integer: the least number of key presses Victor
needs to delete all the e
s.
Constraints
In test cases worth points:
In test cases worth additional points:
Sample Input
35
chefeddiefedjeffeachbigagedegghehad
Sample Output
36
Explanation for Sample Output
An optimal solution for the example test case is:
fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx
Comments