APARTADO 1 (35% sobre el total de la prueba)
La compañía informática
"Bunny"
es consciente que, debido a las premuras habituales de tiempo, normalmente
comercializa
programas que contienen errores ("bugs", en inglés) que
deben
corregirse en sucesivas versiones, añadiendo a dichos programas los
denominados
"parches".
Por desgracia, también los parches se construyen con
prisas,
y por eso un parche que corrige unos errores puede introducir otros nuevos,
que deben corregirse en el futuro con nuevos parches, y así
sucesivamente.
Pero no sólo eso. Para mayor escarnio de la
compañía,
algunos parches exigen que se den determinados errores en la versión
del programa sobre la que deben aplicarse. Ello es debido a que,
internamente,
un parche puede ser tan chapucero como para aprovechar alguna
característica
del programa ligada precisamente a uno de los errores existentes.
Objetivo
Dado un programa cuya versión inicial contiene
algunos
errores, y dado un conjunto de parches, se trata de determinar si es
posible
encontrar una secuencia de aplicación de parches que construya una
versión
del programa libre de errores.
Además, cada parche tiene un coste asociado. Se
pretende
que, en caso de haber más de una solución al problema, se
devuelva
la que tenga un coste menor (el coste de la solución es la suma de
los
costes de los parches que la componen).
Entrada
Residente en el fichero de caracteres "BUG1.DAT",
consiste
de:
* Una primera línea con dos enteros n y m que
representan
el número de errores y el de parches, respectivamente. Supondremos
que
1 <= n <= 10 y 1 <= m <= 26.
* Una segunda línea con el estado inicial del
programa
(es decir, qué errores están presentes y cuáles
ausentes).
Este estado se representa mediante una cadena de exactamente n caracteres.
Si
el carácter i-ésimo de la cadena es ´+´,
significa
que el error i-ésimo está presente en ese estado inicial; si
es
´-´, está ausente.
* A continuación, m líneas describiendo los
parches.
Cada línea contiene cuatro datos: una letra mayúscula que
identifica
el parche (podéis suponer que no hay dos parches identificados por
la
misma letra); un entero estrictamente positivo con el coste del parche; y
dos
cadenas de exactamente n caracteres.
- La primera cadena codifica los errores que deben estar
presentes
o ausentes para poder aplicar el parche. Si el carácter
i-ésimo
de la cadena es ´+´, significa que el error i-ésimo
debe
estar presente; si es ´-´, debe estar ausente; y si es
´0´,
el parche puede aplicarse independientemente de si el error
i-ésimo
está presente o ausente.
- La segunda cadena codifica el estado de los errores
después
de aplicar el parche. Si el carácter i-ésimo de la cadena
es
´+´, el parche introduce (o conserva) el error
i-ésimo;
si es ´-´, el parche asegura que el error i-ésimo
está
ausente; y si es ´0´, el parche no modifica el estado del
error
i-ésimo (si estaba presente antes, lo seguirá estando; y si
estaba ausente, no lo introduce).
Los enteros se representan mediante caracteres, pudiendo
haber
ceros a la izquierda; podéis suponer que aparecen sin signo. En una
misma
línea, los datos estarán separados por uno o más
blancos.
Pueden haber blancos al principio y al final de la línea.
Salida
Residente en el fichero de caracteres "BUG1.RES",
puede
ser de dos tipos:
* Si no se encuentra solución al problema, una
única
línea con dos caracteres, que diga "NO".
* Si se encuentra solución al problema, debe darse la
secuencia de parches de coste mínimo que arregla todos los errores,
en
el orden en que deben aplicarse.
- La primera línea contiene dos enteros. El primer
entero
es el coste de la secuencia, y el segundo su longitud. Ambos enteros
estan
separados por un único blanco, sin ceros a la izquierda y sin
signo.
No debe haber blancos ni al principio ni al final de la
línea.
- Después, tantas líneas como parches
aparecen
en la solución. En cada línea debe aparecer un único
carácter, el identificador del parche aplicado. Los parches deben
aparecer
en el mismo orden en que se aplican. Destaquemos que un mismo parche
puede
aparecer varias veces en la solución (si se aplica en diferentes
momentos...).
En caso de haber más de una solución de coste
mínimo,
puede darse cualquiera de éstas.
Ejemplo de entrada
3 3
+-+
A 06 +-0 --0
B 4 00+ +--
F 12 000 -+-
Ejemplo de salida
10 2
B
A
APARTADO 2 (15% sobre el total de la prueba)
La compañía "Bunny" quiere cotizar
en
bolsa y, para ello, desea optimizar el tratamiento de los parches de la
manera
siguiente.
Se ha comprobado que, debido a las prisas y poca traza con
que
se construyen los parches, muchas veces existen parches que no se usan
nunca.
Se quiere ahora eliminar estos parches.
Más concretamente, el proceso de
simplificación
de parches debe eliminar:
- Los parches que sólo son aplicables sobre
programas
correctos (sin bugs).
- Los parches que no tienen ningún efecto sobre el
estado
del programa.
- Los parches inútiles porque, en las condiciones en
que se pueden aplicar, siempre es posible aplicar algún otro
parche
de menor coste.
Entrada
Similar al apartado 1, pues tan solo desaparece el estado
inicial.
Residente en el fichero de caracteres "BUG2.DAT", consiste
de:
* Una primera línea con dos enteros n y m que
representan
el número de errores y el de parches, respectivamente. Supondremos
que
1 <= n <= 10 y 1 <= m <= 26.
* A continuación, m líneas describiendo los
parches.
Cada línea contiene cuatro datos: una letra mayúscula que
identifica
el parche (podéis suponer que no hay dos parches identificados por
la
misma letra); un entero estrictamente positivo con el coste del parche; y
dos
cadenas de exactamente n caracteres.
- La primera cadena codifica los errores que deben estar
presentes
o ausentes para poder aplicar el parche. Si el carácter
i-ésimo
de la cadena es ´+´, significa que el error i-ésimo
debe
estar presente; si es ´-´, debe estar ausente; y si es
´0´,
el parche puede aplicarse independientemente de si el error
i-ésimo
está presente o ausente.
- La segunda cadena codifica el estado de los errores
después
de aplicar el parche. Si el carácter i-ésimo de la cadena
es
´+´, el parche introduce (o conserva) el error
i-ésimo;
si es ´-´, el parche asegura que el error i-ésimo
está
ausente; y si es ´0´, el parche no modifica el estado del
error
i-ésimo (si estaba presente antes, lo seguirá estando; y si
estaba ausente, no lo introduce).
Los enteros se representan mediante caracteres, pudiendo
haber
ceros a la izquierda; podéis suponer que aparecen sin signo. En una
misma
línea, los datos estarán separados por uno o más
blancos.
Pueden haber blancos al principio y al final de la línea.
Salida
Residente en el fichero de caracteres "BUG2.RES",
consiste
en tantas líneas como parches útiles quedan. En cada
línea
hay un único carácter, el identificador de parche. Los
parches
deben aparecer en orden alfabético.
Ejemplo de entrada
3 5
A 06 --- +-+
B 4 +-0 +00
F 12 --+ ---
D 8 +++ --+
S 3 +0+ --0
Ejemplo de salida
F
S
Observaciones
Notad que los parches pueden ser más enrevesados que
los
casos vistos aquí. Por ejemplo, la información necesaria para
eliminar un parche puede que sea necesario deducirla a partir de más
de un parche.
Notad que los parches no pueden cambiar de forma; o se
eliminan
o se mantienen tal cual, pero no pueden transformarse. | 
