FIFA Fan Festival en la Macroplaza

Es tradición en los mundiales que se habiliten espacios públicos para aquellos aficionados que no consiguieron boletos pero quieren vivir el ambiente mundialista. Este año, la Macroplaza en Monterrey se habilitó como un FIFA Fan Festival en donde los aficionados pueden disfrutar de los partidos de la selección de forma gratuita y en un espacio seguro.

Dado que los meses de junio y julio suelen ser lluviosos en Monterrey, los organizadores le pidieron a Karel que les ayude a poner lonas para proteger a los fánaticos. La Macroplaza tiene casi medio millón de ~m^2~ de superficie y es una de las 5 plazas más grandes de todo el mundo. Por lo que ponerle lonas es más difícil de lo que suena.

Karel, siempre creativo, decidió optimizar la solución. Karel solicitó al gobierno un mapa de la macroplaza que tuviera marcadas las zonas específicas que tenían que estar cubiertas. Karel debe diseñar una posible cobertura que optimice costo y resultados.

IMPORTANTE: Lee con detalle la descripción del problema a continuación.

Problema

El mundo de Karel describe el mapa de la macroplaza. En el mundo hay montones de ~1~ zumbador que representan las áreas que deben quedar cubiertas.

Debes escribir un programa que diseñe una posible cobertura con lonas, los pedazos cubiertos con lona se señalan con montones de ~2~ zumbadores. En la posición (1,1) del mundo hay un montón de zumbadores que define el número ~K~, la cantidad máxima sugerida de rectángulos que puede usar tu cobertura.

Tu cobertura se calificará en base a varios parámetros. A continuación se da la fórmula exacta de evaluación y una descripción conceptual de qué cosas importan.

• Tu calificación será más alta mientras:
  • Mas posiciones cubras. Nota que esto implica que no es obligatorio cubrir todas las posiciones.
  • Menos área cubras.
  • Menos rectángulos de lona uses.

La fórmula exacta de evaluación es la siguiente:

• Sea ~N~ el número de casillas que hay que cubrir.
• Sea ~C~ el número de casillas que cubre tu programa. Recuerda que no tienen que ser todas.
• Sea ~A~ el área total que cubre tu programa.
• Sea ~K~ el número máximo sugerido de rectángulos que puedes usar.
• Sea ~R~ un número que representa la cantidad de rectángulos y que se calcula con la siguiente fórmula:
  • ~R = \frac{T}{4} + H~
  • Donde ~T~ es la cantidad de esquinas en el área que cubriste.
  • Y ~H~ es la cantidad de huecos encerrados en el área que cubriste.

Para calificarte, el evaluador calcula el siguiente parámetro:

~cobertura = 100 \cdot \left( \frac{C}{N} \right) ^2 \cdot \left( \frac{C}{A} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{R - 1}{K} \right) ^2 \right)~

Tu puntaje final para el caso dependerá del valor que obtengas en ~cobertura~. En específico:

• Si tu ~cobertura >=~ solución oficial obtendrás 100% de los puntos.
• Si tu ~cobertura <=~ mínimo oficial obtendrás 0% de los puntos.
• Si tu ~cobertura~ está entre ambos valores obtendrás un puntaje proporcional.

Para que sea más clara la forma de evaluación te recomendamos ver los ejemplos de entrada y salida.

Entrada

Observa que en el mundo de ejemplo hay ~N = 6~ casillas por cubrir y el máximo sugerido de rectángulos ~K = 3~.

Salida

A continuación se muestran múltiples coberturas posibles y el puntaje que obtendría cada una de ellas de acuerdo a la fórmula.

En este ejemplo se decidió cubrir todo el mundo. Los parámetros de la fórmula son:

• ~C = 6~, se cubrieron las 6 casillas deseadas.
• ~A = 120~, se cubrió un área total de ~10 \times 12 = 120~ casillas.
• ~R = 1~, hay 4 esquinas de 90 grados en la zona de cobertura y no hay huecos encerrados.

~cobertura = 100 \cdot \left( \frac{C}{N} \right) ^2 \cdot \left( \frac{C}{A} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{R - 1}{K} \right) ^2 \right) = 100 \cdot \left( \frac{6}{6} \right) ^2 \cdot \left( \frac{6}{120} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{1 - 1}{3} \right) ^2 \right) = 100 \cdot (1)^2 \cdot (0.05)^8 \cdot (1 - (0.3)(0)) = 9.1~

En este ejemplo se decidió cubrir todas las zonas pero con un rectángulo más pequeño, cómo el área es menor, el puntaje mejora. Los parámetros de la fórmula son:

• ~C = 6~, se cubrieron las 6 casillas deseadas.
• ~A = 56~, se cubrió un área total de ~7 \times 8 = 56~ casillas.
• ~R = 1~, hay 4 esquinas de 90 grados en la zona de cobertura y no hay huecos encerrados.

~cobertura = 100 \cdot \left( \frac{6}{6} \right) ^2 \cdot \left( \frac{6}{56} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{1 - 1}{3} \right) ^2 \right) = 100 \cdot (1)^2 \cdot (0.1071)^8 \cdot (1 - (0.3)(0)) = 16.75~

En este ejemplo se decidió utilizar 2 rectángulos en vez de uno. Disminuir el área cubierta te mejora el puntaje, pero aumentar el número de rectángulos lo disminuye.

• ~C = 6~, se cubrieron las 6 casillas deseadas.
• ~A = 44~, se cubrió un área total de ~44~ casillas entre ambos rectángulos.
• ~R = 2~, hay 8 esquinas de 90 grados en la zona de cobertura y no hay huecos encerrados.

~cobertura = 100 \cdot \left( \frac{6}{6} \right) ^2 \cdot \left( \frac{6}{44} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{2 - 1}{3} \right) ^2 \right) = 100 \cdot (1)^2 \cdot (0.1364)^8 \cdot (1 - (0.3)(\frac{1}{3})^2) = 19.64~

En este ejemplo se decidió dejar una casilla sin cubrir y optimizar el área de cobertura. Las flechas rojas en la región superior izquierda muestran las esquinas de 90 grados en esa región de cobertura.

• ~C = 5~, faltó una casilla de cubrir.
• ~A = 15~, el área total cubierta es de ~15~ casillas.
• ~R = 3~, hay 12 esquinas de 90 grados en la zona de cobertura y no hay huecos encerrados.

~cobertura = 100 \cdot \left( \frac{5}{6} \right) ^2 \cdot \left( \frac{5}{15} \right)^{0.8} \cdot \left( 1 - 0.3 \left( \frac{3 - 1}{3} \right) ^2 \right) = 100 \cdot (0.8334)^2 \cdot (0.3334)^8 \cdot (1 - (0.3)(\frac{2}{3})^2) = 24.99~

Esta solución muestra cómo se contabilizaría una región con un hueco encerrado.

• ~C = 4~, faltaron dos casilla de cubrir.
• ~A = 18~, el área total cubierta es de ~18~ casillas.
• ~R = 3~, hay 8 esquinas de 90 grados, 4 externas y 4 internas y hay un hueco encerrado.

Consideraciones

• Karel inicia en la posición (1, 1) viendo al norte.
• Karel lleva infinitos zumbadores en la mochila$.
• En la posición (1,1) del mundo hay un montón de zumbadores que representa el número ~K <= 8~. Si tu solución utiliza más de ~K~ rectángulos tu puntaje será muy bajo.
• En el mundo hay montones de ~1~ zumbador que representan las áreas a cubrir.
• El mundo de Karel es rectangular y sin paredes internas. Sus dimensiones máximas son de ~40 x 40~.

Subtareas

En este problema, los casos de cada subtarea se encuentran agrupados. El puntaje que recibas en cada subtarea será el del caso en el que obtuviste el menor puntaje del grupo.

• Subtarea 1 (25 puntos): ~N = K~
• Subtarea 2 (25 puntos): Hay ~K~ grupos conexos de montones de ~1~ zumbador en el mundo.
• Subtarea 3 (25 puntos): Hay ~K~ regiones densas en zumbadores, no necesariamente conexos, en el mundo.
• Subtarea 4 (25 puntos): Sin restricciones adicionales.