Typematrix P23444

El profesor Oak a menudo reta a sus alumnos a programar más rápido que él. “Mirad”, dice, “no puede ser tan dífícil, yo tecleo con sólo dos dedos”. Pero pocos alumnos le ganan: en parte, porque el profesor Oak tiene su experiencia programando, pero también porque el profesor Oak ha perfeccionado el arte de escribir con dos dedos.

Un alumno puso delante del profesor Oak un teclado Typematrix como el siguiente,

donde las teclas están dispuestas en una matriz, y le pidió al profesor Oak que tecleara una palabra formada por letras mayúsculas, tan rápido como le fuera posible.

“¿Tan rápido como sea posible?”, dijo el profesor. “De acuerdo, dame un momento para pensarlo.” Y en efecto, unos segundos más tarde, el profesor Oak se puso a teclear la palabra.

El alumno se quedó sorprendido al ver que el profesor Oak rompía otra regla básica de la mecanografía: ¡usaba ambos dedos en ambas partes del teclado, según le convenía! Cuando el alumno le indicó esto al profesor, este le respondió enfadado: “¡Pues claro! Pensaba que me habías pedido que lo hiciera tan rápido como fuera posible. Si lo que querías es que usara un dedo en las 15 letras de la parte izquierda del teclado, y el otro dedo en las 11 letras de la derecha, no hubiera tenido que perder unos valiosos segundos pensando el problema.”

Sabiendo que los dedos del profesor Oak empiezan, respectivamente, sobre las teclas Q y Y; que el profesor tarda 1 milisegundo en desplazar un dedo una tecla de distancia (en cualquiera de las cuatro direcciones) o en apretar una tecla; y que nunca mueve ambos dedos a la vez, calcula cuántos milisegundos tardara el profesor en escribir la palabra con y sin la restricción descrita.

Por ejemplo, si la palabra es HOLOHOLO y cada dedo está restringido a su zona del teclado, el profesor Oak tardaría 1 milisegundo en mover el dedo derecho a la H, otro milisegundo en apretarla, 4 milisegundos en mover el dedo derecho a la O, otro milisegundo en apretarla, etc., hasta un total de 25 milisegundos. Por contra, si pudiera usar los dos dedos libremente, el profesor Oak sólo tardaría 22 milisegundos: mover el dedo izquierdo a la H le cuesta 7 milisegundos, pero una vez está allá, puede usar ese mismo dedo izquierdo para la segunda H, mientras que el dedo derecho se encargaría de las letras O y L.

Entrada

La primera línea de la entrada contiene el número k, que puede ser 1 o 2. A continuación, una línea por cada caso, con una palabra con como mucho 100 letras mayúsculas. Nunca habrá más de 100 casos por entrada.

Salida

Para cada caso, escribe una línea con el número de milisegundos que tardará el profesor Oak en teclear la palabra. Si k=1, asume que cada dedo tiene asignada una zona del teclado; si k=2, los dedos pueden moverse libremente por todo el teclado.

Puntuación

• TestA:  ‍ Entradas con k=1.  ‍40 Puntos ‍

• TestB:  ‍ Entradas con k=2, ninguna palabra tiene más de 10 letras.  ‍30 Puntos ‍

• TestC:  ‍ Entradas con k=2.  ‍30 Puntos ‍