Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está haciendo las prácticas en una fábrica de ejes. Los objetos producidos en este lugar son usados en las grandes industrias, centrales y termoeléctricas. Los ejes producidos en la fábrica pueden ser de distintos tipos. Para conocer el tipo de un eje, este se divide en secciones preestablecidas y cada sección tiene una letra que la identifica. Estas letras son un convenio internacional que le permite al usuario saber cómo está compuesto el eje,  simplemente viendo las letras que lo conforman.

El problema que le presentan a Fito tiene que ver con el mantenimiento de las máquinas que hacen los ejes. Debido al deterioro y la negligencia, se tiene que todas las máquinas están en muy mal estado y se determina cerrar la industria por un mes. La idea es dar mantenimiento a las máquinas durante ese tiempo y después abrir nuevamente la fábrica. Sin embargo un mes es muy poco tiempo para reponerlas a todas,  por lo que se decide arreglar las que son imprescindibles primero y después de abrir  dar mantenimiento al resto según sea posible.

En este momento Fito debe hacer un algoritmo que le diga la menor cantidad de máquinas necesarias, para producir todos los tipos de ejes que puede hacer la fábrica. Cada tipo de eje es hecho con una máquina distinta pero hay otra forma de hacer un eje. Por ejemplo si necesitamos hacer un eje de tipo “abcd” y tenemos una máquina para hacer ejes de tipo “ab” y otra para los de tipo “cd”, entonces haciendo uno de cada uno podemos unir los resultados y obtener un eje del tipo buscado. En este caso la máquina que hace los ejes de tipo “abcd” no es imprescindible y por tanto se puede dejar su mantenimiento para después de abrir la fábrica. Los ejes pueden ser unidos cualquier cantidad de veces pero no pueden ser divididos.