COMPETICION EN EL LABORATORIO Un laboratorio de investigación médica desea llevar a cabo una serie de experimentos para probar diversos agentes inmunológicos. Dichos agentes son esencialmente organismos, compuestos por células sintéticas, que pueden representar anticuerpos, vacunas, virus, etc. Nos han encargado un programa para simular las reacciones de dichos agentes cuando interactúan unos con otros, de modo que el laboratorio pueda realizar gran número de experimentos sin necesidad de emplear agentes reales, con el consiguiente ahorro de tiempo y materiales. Tened en cuenta que hoy en día existe una gran demanda de soluciones para diversas enfermedades y cualquier aportación para mejorar la investigación en este campo es muy valiosa. Un experimento típico se organiza de la siguiente manera. Al inicio, se dispone de un número N de organismos, numerados correlativamente desde 1 en adelante (N es un natural mayor o igual que 2). A continuación, se van emparejando dichos organismos de diversas maneras para estudiar las reacciones a que cada emparejamiento (también podemos decir "enfrentamiento") da lugar. Cuando se hayan enfrentado todos contra todos, se dice que se ha completado una ronda de enfrentamientos. Un experimento puede constar de cualquier número de rondas. Por otra parte, después de cada ronda será posible mejorar los organismos (también podemos decir "evolucionar"), aplicándoles ciertas sustituciones de células. Para ello, se dispone en el sistema de un conjunto adicional, no acotado, de células sueltas (también podemos llamarlas "libres"). Debido a la posibilidad de evolución de los organismos, los resultados de un enfrentamiento entre un mismo par de organismos realizado en diferentes rondas pueden ser diferentes. Notad que los organismos no mueren ni desaparecen del sistema. El programa ha de gestionar los mencionados experimentos (rondas de enfrentamientos y evoluciones) y proporcionar mecanismos para la consulta de los resultados. Estructura de un organismo: Un organismo se compone de un conjunto de células conectadas entre sí. Cada organismo posee una primera célula, llamada madre, que puede estar conectada con un máximo de otras dos células, llamadas sucesoras izquierda y derecha; cada una de éstas puede tener a su vez un máximo de dos sucesoras y así sucesivamente. Una misma célula no puede ser sucesora de sus sucesoras, o de las sucesoras de sus sucesoras, etc. Por su parte, todas las células (es decir, las de los organismos y las libres) se clasifican en T tipos diferentes, que denotamos por los valores 1..T (T es un natural mayor o igual que 1). Un organismo puede contener una célula de cada tipo como máximo. Notad que el número de células de un organismo puede ser mucho más pequeño que T. Cada tipo de células posee una "calidad", que será la que contribuirá a que el organismo al que pertenece tenga más opciones de vencer a los otros. Dicha calidad se expresa en términos de un número natural. Enfrentamiento entre organismos: Cuando se enfrentan dos organismos, el resultado se decide de la siguiente manera. Para empezar, se obtiene para cada organismo el mayor "suborganismo" del mismo que "encaja" en el otro, es decir, el mayor subconjunto conectado de sus células, incluyendo obligatoriamente a su célula madre, tal que el otro organismo posee una célula en la misma posición. Ejemplo: en los organismos abajo representados, la sucesora izquierda de una célula es la que cuelga a su izquierda y la sucesora derecha es la que cuelga a su derecha. Cada célula se denota por su tipo. Si tenemos 31 41 / \ / \ O3 = 32 33 O4 = 42 43 / / \ 34 35 44 nos quedamos con 31 41 / \ / \ O3aux = 32 33 O4aux = 42 43 Ahora, cada suborganismo puede elegir una de las células de su correspondiente organismo que han quedado descartadas en el proceso anterior y usarla para sustituir una célula de las que tiene. El criterio de sustitución se basa en las calidades de los tipos de las células: sustituimos la de menor calidad del suborganismo por la de mayor calidad entre las descartadas, si ésta es de mejor calidad que aquella. En caso contrario, no se realiza ninguna sustitución. En caso de que haya varios tipos empatados a calidad, se toma el de identificador más pequeño. Por ejemplo, supongamos que O3aux cambia la 32 por la 35 y que O4aux no cambia 31 41 / \ / \ O3aux = 35 33 O4aux = 42 43 Por último, contamos el número de células de cada suborganismo que tienen más calidad que su correspondiente del otro, es decir, el número de células de cada suborganismo que "venzan" a su correspondiente del otro. Decimos que un organismo X vence a otro organismo Y si el número de células del suborganismo de X que superan a su correspondiente en el suborganismo de Y es estrictamente mayor que las que son superadas. El empate a células vencedoras equivale al empate entre organismos. En el ejemplo anterior, si suponemos que las células 31 y 35 tienen más calidad que la 41 y la 42 respectivamente, pero la 43 tiene más calidad que la 33, el vencedor es O3, por 2 a 1. Notad que el enfrentamiento entre dos células es una operación conmutativa: dadas dos células A y B cualesquiera, la vencedora de enfrentar a A contra B es la misma que la de enfrentar a B contra A. Por extensión, el enfrentamiento entre dos organismos también es conmutativo. Clasificación de una ronda: Para cada ronda se establece un ranking o clasificación de los organismos, basado en el siguiente sistema de puntuación: cada victoria proporciona 3 puntos al organismo ganador y 0 al perdedor; cada empate proporciona 1 punto a cado organismo. De cara a resolver posibles empates a puntos, se consideran las diferencias entre el número de células ganadoras y perdedoras de cada organismo a lo largo de todos los enfrentamientos de la ronda. Si persiste el empate, queda en mejor posición el organismo con menor identificador. Rendimiento de un tipo de células en una ronda: A lo largo de los diversos enfrentamientos de una ronda contabilizaremos las victorias, derrotas y empates de los representantes de cada tipo de células. Si se enfrenten dos células del mismo tipo, se anotan un empate *cada una*. Además, cada victoria de una célula en un enfrentamiento ganado por el organismo que la contiene le supondrá a su tipo un bonus de 0,2 victorias. De esta forma, si tras una ronda llamamos NV a su número de victorias, NE a su número de empates, ND a su número de derrotas y B a la suma de sus bonus, definimos el rendimiento de un tipo así a) si el tipo ha participado en algún enfrentamiento, R = parte entera [(NV + B + 0.5*NE) * 100 / (NV + ND + NE)] - 50 b) en caso contrario, R = 0 Ejemplo: si a lo largo de los enfrentamientos de una ronda un tipo de células ha tenido 6 victorias, de las cuales 3 han sido en organismos ganadores (con lo que su bonus es 0,6), 2 empates y 3 derrotas, su rendimiento habrá sido p.e. [(6 + 0,6 + 1) * 100 / (6 + 3 + 2)] - 50 = p.e.(760/11)-50 = 69-50 = 19 El rendimiento será considerado como el porcentaje de mejora que ha tenido un tipo de células en una ronda. Lo usaremos para actualizar las calidades de los tipos de células y, más adelante, para aplicar mejoras en los organismos. Actualización de las calidades de los tipos de células: Después de una ronda, la "nueva" calidad de un tipo de células se calcula así, usando el rendimiento (R) de la ronda anterior calidad nueva = parte entera [calidad antigua * (1+R/100)] En el ejemplo anterior si la calidad antigua del tipo era 36, la nueva será p.e. [36*(1+0.19)] = 42 Obviamente, el rendimiento puede ser negativo, en cuyo caso se producirá una pérdida de calidad. Evolución de un organismo: Al terminar una ronda, se permite a cada organismo sustituir como máximo sus dos células de peor rendimiento por células libres, en las condiciones que mencionamos a continuacion. Para equilibrar el estado del experimento, las mejoras se realizarán en orden inverso al ranking de los organismos: primero tendrá oportunidad de mejorar el peor organismo, después el segundo peor (con las células libres en el estado que dejó el primero), etc. A cada tipo de células se le asignará un precio por célula. Inicialmente, dicho precio será igual a 1000 multiplicado por su calidad. Tras cada ronda, el precio se actualizará mediante dicha proporción, pero con restricciones: el nuevo precio no podrá ser ni mayor que el 120%, ni menor que el 80%, del antiguo. En los casos donde se apliquen estas limitaciones hay que tomar la parte entera del resultado. A cada organismo se le asignará un cierto presupuesto al principio del experimento, que podrá usar para cambiar sus células tras cada ronda. Cada célula sustituida aporta su precio al presupuesto y cada célula nueva resta su precio del presupuesto. La manera exacta en la que se realizará la sustitución de células es la siguiente: 1) Se obtienen las dos células con peor rendimiento en la ronda anterior (C1 y C2). En caso de empate, tienen prioridad las células con menor identificador de tipo. 2) Se calcula la mayor mejora de rendimiento respecto a C1 y/o C2 que se puede obtener con una o dos células libres, tales que puedan ser pagadas por el organismo y no queden repetidas en el mismo. La o las células libres que produzcan la máxima mejora de rendimiento sustituyen a C1 y/o C2 en el organismo. Ejemplo: Consideremos un organismo que dispone de un presupuesto de 100000 y sus peores células son (R=rendimiento y P=precio): C1: R=15 P=10000 C2: R=20 P=25000 y las células libres con disponiblidad mayor que 0 son L1: R=10 P=20000 L2: R=25 P=25000 L3: R=35 P=30000 Si no hay problemas de células repetidas, hay que cambiar C1 y C2 por L2 y L3, ya que producen la máxima mejora de rendimiento (25). El presupuesto se reduce a 80000 (100000+10000+25000-25000-30000). Notad que, en estas condiciones, no es descartable que la sustitución preferida sea con una sola célula libre, en vez de con dos y, en ese caso, puede que no se sustituya necesariamente la peor célula antigua, ya sea por restricciones presupuestarias, falta de disponibilidad, etc. (imaginad el ejemplo anterior con presupuesto igual a 0). Incluso puede ocurrir que no haya ninguna sustitución que dé lugar a mejora. En caso de que la mejora máxima sea realizable con más de una combinación de células nuevas, se elige la más económica, es decir, aquella que haga que el presupuesto resultante sea mayor. Si aún hay empate, tienen preferencia las que impliquen dos cambios. Si hay empate entre éstas, nos quedamos con la que tenga la célula con el identificador más pequeño y, si aún hay empate, elegimos la que tenga su mayor identificador más pequeño. Si hay empate entre las opciones de un solo cambio, se elige la de menor identificador. En caso de cambiarse las dos células, la nueva del tipo de identificador más pequeño se coloca en la posición de la antigua del tipo de identificador más pequeño. Veámoslo en el siguiente ejemplo Organismo: Células libres: tipo unidades disponibles 3 1 2 / \ 2 3 2 5 3 6 / \ \ 4 1 7 4 6 5 0 6 2 7 1 8 4 Supongamos que el 2 y 6 son los peores tipos de las células del organismo en la ronda anterior y que los tipos 1 y 8 son los que producen más mejora dentro del presupuesto. Entonces el 1 sustituye al 2 y el 8 al 6. La sustitución quedaría Organismo: Células libres: tipo unidades disponibles 3 1 1 / \ 2 4 1 5 3 6 / \ \ 4 1 7 4 8 5 0 6 3 7 1 8 3 Por último, no pueden sustituirse dos células por una o una por dos. SE PIDE Diseñar un programa modular razonablemente eficiente que gestione los procedimientos arriba descritos para un experimento. En primer lugar, deberá leer la situación de partida, es decir, la información relativa al grupo inicial de organismos y células libres. Después tendrá que ir procesando las diversas tareas que se le pidan. Estas podrán ser las siguientes: 1) Realizar una ronda de enfrentamientos 2) Obtener el resultado del último enfrentamiento entre dos organismos 3) Obtener el ranking de todos los organismos en la última ronda realizada 4) Actualizar las calidades de los tipos de células y, en consecuencia, sus precios; informar de los rendimentos de todos los tipos de células. 5) Evolucionar los organismos 6) Consultar la estructura de células de un organismo tras una evolución 7) Modificar el presupuesto de un organismo 8) Modificar la calidad de un tipo de células y, en consecuencia, su precio 9) Modificar la disponibilidad de celulas libres de un tipo de células 10) Consultar los atributos de un tipo de células (calidad, precio y unidades libres; número de victorias totales, empates, derrotas y victorias que dan lugar a bonus, en la última ronda) 11) Consultar el presupuesto de un organismo. Notad que hay ciertas restricciones lógicas en el orden que estas operaciones se pueden aplicar. Las opciones 4 y 5 no se aplicarán antes de la primera ronda. Posteriormente, la 4 ha de aplicarse antes que la 5, ambas se aplicarán exactamente una vez entre rondas y las operaciones 6-9 sólo se aplicarán después de la 5. Más adelante podremos añadir más consultas a elementos del sistema implicados en los procesos anteriores. La forma de comunicarnos con el programa para que realice dichas tareas será parecida a la de los casos de estudio de teoría: "Cubeta", "Experimentos Inmunológicos", etc. Podéis diseñar un esquema provisional que ya refinaréis cuando conozcáis el juego de pruebas público. En días sucesivos se completarán los detalles que se hayan podido pasar por alto en este enunciado y se publicarán las aclaraciones oportunas. La sintaxis *exacta* de los datos y resultados, acompañada del juego de pruebas público, se conocerá dos semanas antes del día de la entrega del programa C++. Hasta entonces no podréis implementar de forma definitiva las operaciones de lectura y escritura necesarias para los tipos que utilicéis, aunque sí podréis especificarlas. Podéis consultar el ejemplo del cuatrimestre anterior para tener una idea aproximada.