La Facultad Oficial de Camareros Atildados (FOCA) ha decidido incluir una prueba práctica en el examen previo a la obtención del título de camarero, que intenta medir la agilidad mental de los aspirantes a dicho título. La prueba consiste en trasvasar parte del líquido residente en unos recipientes a otros recipientes, obviamente sin derramar una gota. A la especificación del estado de los recipientes al empezar el proceso lo llamaremos configuración inicial, y a la configuración del estado al acabar, configuración final. En ambas configuraciones, los recipientes pueden estar totalmente llenos, parcialmente llenos o vacíos; además, puede haber recipientes que aparezcan en la configuración inicial pero no en la configuración final, lo que significa que el estado final de dichos recipientes no es relevante de cara a la solución del problema. Los recipientes se identifican mediante una letra mayúscula (es decir, hay un máximo de 26, pues no se consideran ni la 'Ñ' ni la 'Ç'). Se conoce la capacidad de cada uno de los recipientes (entre 1 y 99 cl.), y también la cantidad inicial de cada uno de los recipientes de partida (entre 0 y 99 cl.).

Uno de los estudiantes, Guille Puertas, decide llevarse a la prueba una chuleta informática en forma de programa capaz de realizar este cálculo, y os pide su construcción.

Apartado 1

Construir un programa que analice la corrección de una entrada compuesta por una pareja de configuraciones iniciales y finales. Esta entrada residirá en un fichero de caracteres "REC1.DAT" que tendrá el formato siguiente:

• en la configuración inicial, habrá una línea para cada uno de los recipientes que intervienen (sin repeticiones, y sin ningún tipo de orden predeterminado) que constará de:
  - identificador del recipiente (letra mayúscula)
  - carácter blanco
  - capacidad del recipiente (uno o dos dígitos -caracteres entre el '0' y el '9')
  - carácter blanco
  - contenido inicial (uno o dos dígitos), menor o igual que su capacidad
• a continuación, una línea que contendrá un único carácter '=', que sirve como separador de las dos configuraciones
• y después, la configuración final, que también contendrá una línea por recipiente y sin repetir recipientes (igualmente sin ningún tipo de orden predeterminado, y no necesariamente en el mismo orden que en la configuración inicial), aunque estas líneas no incluirán la capacidad, con lo que su formato será:
  - identificador del recipiente (letra mayúscula)
  - carácter blanco
  - contenido final (uno o dos dígitos)
  

El fichero de salida "REC1.RES" contendrá una línea con un único carácter entre '0' y '6', que codifica la corrección o no de la entrada y, en caso de incorrección, determina la causa. En concreto, la salida debe ser:

0. la entrada es correcta
1. en alguna de las configuraciones, se dice que algún recipiente está lleno por encima de su capacidad
2. existe algún recipiente repetido en la configuración inicial o en la configuración final
3. la configuración final incluye algún recipiente que no aparece en la configuración inicial
4. hay más líquido en la configuración final que en la inicial
5. o bien falta la configuración inicial, o bien la final, o bien ambas
6. cualquier otro tipo de error, que podrá calificarse como error de formato en el fichero (por ejemplo, identificador de recipiente que no sea letra mayúscula, o caracteres extraños en una línea, o capacidad fuera de los límites permitidos)

Podéis suponer que nunca habrá más de un error en el fichero de entrada. Presentamos a continuación diversos ejemplos de fichero:

Apartado 2

Construir un programa que obtenga la secuencia mínima de movimientos unitarios de líquido que lleve de la configuración inicial a la final, pasando en el caso general por diversas configuraciones intermedias. Se entiende por movimiento unitario el trasvase de líquido proveniente del recipiente a al recipiente b hasta que o bien a queda vacío o bien b queda lleno (pudiéndose cumplir ambas condiciones simultáneamente). Está prohibido cualquier movimiento que no satisfaga estas condiciones. En caso de haber más de una secuencia mínima, puede devolverse como resultado cualquiera de ellas. También debe detectarse la imposibilidad de satisfacer la petición. Puede suponerse que la información de entrada es correcta.

El programa leerá la información del fichero "REC2.DAT" que tendrá el mismo formato que el fichero "REC1.DAT" del apartado anterior. Como resultado, debe generarse un fichero "REC2.RES" que contenga una línea para cada uno de estos movimientos unitarios, y tales que los movimientos aparezcan en el mismo orden en que se aplican. Cada línea constará de:

• identificador del recipiente del que parte el líquido (letra mayúscula)
• carácter blanco
• identificador del recipiente de destino (letra mayúscula)

En caso que no se pueda encontrar ninguna secuencia, la salida contendrá una única línea con la palabra 'NO' (en mayúsculas, sin ningún otro carácter).
La figura siguiente muestra un ejemplo de fichero de entrada con tres recipientes de capacidades 8, 5 y 3 tales que el primero de ellos parte con 8 cc. (es decir, está inicialmente lleno), pidiéndose en la configuración de destino que los otros dos recipientes queden. Se muestra en "REC2.RES" una posible salida generada (en este ejemplo, también es valida la misma salida intercambiando el orden de las líneas):

Apartado 3

Finalmente, dada solamente una configuración final de recipientes, se pide que averigüéis qué configuración inicial exige una secuencia mínima de movimientos unitarios para llegar a la configuración final dada suponiendo que en la configuración inicial todos los recipientes han de estar totalmente llenos o totalmente vacíos. En la configuración final no se contempla ningún tipo de restricción sobre el contenido de los recipientes: pueden estar totalmente llenos, totalmente vacíos o parcialmente llenos.

En caso de existir más de una solución mínima, se elegirá aquella que minimice el número de recipientes de la configuración inicial. Si incluso con este criterio sigue habiendo empates, se minimizará la suma de líquido contenido en los recipientes de la configuración inicial. Y si aún así hay más de una, entonces cualquiera de ellas será una solución válida.

La entrada será el fichero "REC3.DAT" que contendrá:

• primero, el listado de todos los recipientes disponibles con su capacidad correspondiente: letra mayúscula, carácter blanco y uno o dos caracteres para representar la capacidad
• después, una línea conteniendo únicamente un carácter '='
• finalmente, la configuración final con el formato habitual: letra mayúscula, carácter blanco y uno o dos caracteres para representar la capacidad del estado final.

En la salida "REC3.RES", aparecerán los recipientes no vacíos de la solución, ordenados alfabéticamente, cada uno en una línea diferente que no contenga más caracteres. En caso que el problema no tenga solución, debe aparecer una única línea que contenga la palabra 'NO'. Un ejemplo de este apartado serían los ficheros: