Minimizando hashes
En los primeros sistemas de control de versiones, como RCS, CVS o Subversion, los commits (o versiones del estado del proyecto) se etiquetaban con números enteros consecutivos. Así, el primer commit era el 1, el siguiente era el 2, etc.
En la actualidad es mucho más habitual que cada commit se identifique utilizando una hash: una cadena de un número fijo de caracteres, todos ellos letras o números, y que se extrae de las propiedades del propio commit (como los cambios, hora del commit, identificador del commit "padre" inmediatamente anterior, etc.).
Aunque el uso de estas cadenas tiene sus ventajas, para un humano son bastante "opacas" (a la vista de la hash, poco se puede deducir) y difíciles de escribir para referirse a commits concretos. Para aliviar esta última parte, algunos de estos sistemas permiten identificar cada commit con los primeros caracteres de la cadena, siempre y cuando no haya ningún otro identificador que comience igual.
Entrada
La entrada está formada por distintos casos de prueba. Cada caso comienza con un número indicando el número de commits (o hashes) que hay almacenados en el sistema de control de versiones (hasta 100.000).
A continuación aparecen tantas líneas como commits, cada una con una hash. Por simplicidad, estarán formadas únicamente por las letras a y b y no tendrán más de 30 caracteres. Se garantiza que no habrá dos cadenas iguales y que ninguna cadena será prefijo de otra.
Tras el último caso de prueba viene una línea con un 0 que no debe procesarse.
Salida
Por cada caso de prueba se escribirá un número con el número total de caracteres que habrá que escribir como mínimo para identificar todos los commits.
Entrada de ejemplo
2 a b 3 bb aaaaaa abbaaaaaaa 1 bbb 0
Salida de ejemplo
2 5 0