Escritura


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Un equipo de investigación está desarrollando una nueva tecnología para ahorrar tiempo al escribir mensajes de texto en dispositivos móviles. Un usuario siempre necesita presionar P teclas para escribir una palabra de longitud P.

Sin embargo, esto no es lo suficientemente rápido. El equipo creará un diccionario con las palabras comunes que un usuario puede escribir. El objetivo es reducir el número promedio de teclas necesarias para escribir las palabras que están en el diccionario. Durante la escritura de una palabra, cada vez que se determina de forma exclusiva la siguiente letra, el sistema del teléfono la ingresará automáticamente, sin la necesidad de presionar una tecla. Para ser más precisos, el comportamiento del sistema del teléfono celular estará determinado por las siguientes reglas:

  1. El sistema nunca adivina la primera letra de una palabra, por lo que la primera letra siempre se debe ingresar manualmente presionando la tecla correspondiente.

  2. Si una sucesión no vacía de letras c_1, c_2, \ldots, c_n se ha ingresado, y hay una letra c tal que cada palabra en el diccionario que comienza con c_1, c_2, \ldots, c_n también comienza con c_1, c_2, \ldots, c_n, c, entonces el sistema introduce c de forma automática, sin la necesidad de pulsar una tecla. De lo contrario, el sistema espera al usuario.

Por ejemplo, si el diccionario está compuesto por las palabras "hello", "hell", "heaven" and "goodbye", y el usuario presiona "h", el sistema ingresará "e" automáticamente, porque cada palabra que comienza con "h" también comienza con "he". Sin embargo, dado que hay palabras que comienzan con "hel" y con "hea", el sistema ahora necesita esperar al usuario. Si el usuario presiona "l", obteniendo la palabra parcial "hel", el sistema ingresará una segunda "l" automáticamente. Cuando tiene "hell" como entrada, el sistema no puede adivinar, porque es posible que la palabra haya terminado, o también es posible que el usuario quiera presionar "o" para obtener "hello". De esta manera, para escribir la palabra "hola" el usuario necesita tres teclas, "hell" requiere dos, y "heaven" también requiere dos, porque cuando la entrada actual es "hea" el sistema puede ingresar automáticamente el resto de la palabra aplicando repetidamente la segunda regla. Del mismo modo, la palabra "goodbye" necesita solo una pulsación de tecla, ya que después de presionar la "g" inicial, el sistema completará automáticamente la palabra completa. En este ejemplo, la cantidad promedio de teclas necesarias para escribir una palabra en el diccionario es (3 + 2 + 2 + 1) / 4 = 2.00.

Su tarea es, dado un diccionario, calcular la cantidad promedio de teclas necesarias para escribir una palabra en el diccionario con el nuevo sistema de teléfono celular.

Entrada

La primera línea contiene un número entero N que representa el número de palabras en el diccionario (1 \leq N \leq 10^5). Cada una de las siguientes N líneas contiene una cadena no vacía de como máximo 80 letras minúsculas del alfabeto inglés, lo que representa una palabra en el diccionario. Todas las palabras en el diccionario son diferentes, y la suma de las longitudes de todas las palabras es como máximo 10^6.

Salida

Como salida imprima una línea con un número racional que represente la cantidad promedio de teclas necesarias para escribir una palabra en el diccionario. El resultado debe mostrarse como un número real con exactamente dos dígitos después del punto decimal, redondeado hacia arriba si es necesario.

Ejemplos

Entrada 1
4
hello
hell
heaven
goodbye
Salida 1
2.00
Entrada 2
3
hi
he
h
Salida 2
1.67
Entrada 3
7
structure
structures
ride
riders
stress
solstice
ridiculous
Salida 3
2.71

Comments

There are no comments at the moment.