Restaurante
6 soluciones
500 puntos
Eres el gerente de un restaurante. A la hora del almuerzo, grupos de comenzales llegan y necesitas proveerles mesas. El restaurante tiene mesas de diferentes tamaños para responder a la demanda de grupos de diferente tamaños. Las mesas son proveídas de la siguiente manera:
Cuando un grupo de clientes llega, se le asigna la mesa libre de menor tamaño que pueda proveer espacio a todo el grupo. Solo los tamaños de las mesas son diferentes, así que si hay multiples mesas apropiadas, una es escogida arbitrariamente. Si no hay mesas apropiadas disponibles cuando un grupo llega al restaurante, el grupo es immediatamente rechazado y nunca más retornará. Cuando un grupo termina de comer y se va, su mesa queda disponible nuevamente para ser usada para otro grupo de comenzales.
Los grupos se listaran en el orden que ellos llegan al restaurante, y ningun otro grupo llegará en el mismo tiempo. Si un grupo llega a la misma hora que un grupo se va, la mesa del grupo que esta saliendo estará disponible para el grupo entrante (Mire el primer ejemplo). Retorne el número de comenzales que son rechazados.
Input
La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 <= M <= 100)
Por cada caso vienen 4 lineas, descritas a continuación:
En la primera linea viene el tamaño de las mesas. Entre 1 y 50 (incluídos) mesas es posible. Y cada mesa alojará entre 1 y 20 personas, incluídos.
En la segunda linea viene la lista de los grupos de comenzales que vendrán a lo largo del día. Entre 1 y 50 (incluídos) grupos de comenzales es posible. Cada grupo puede ser conformado entre 1 y 20 personas.
En la tercera y cuarta linea viene el tiempo de llegada y partida de cada grupo.
La 2da, 3ra y 4ta linea tendran el mismo numero de elementos (separados por un espacio)
El tiempo de llegada y salida de cada grupo puede estar entre 0 y 200.
Los tiempos de llegada seran estrictamente menores a los tiempo de partida.
Los tiempos de llegada seran distintos y en orden ascendente.
Output
Retorna el número de personas que fueron rechazadas del restaurante.
Entrada de ejemplo
Input |
2 |
Output |
14 |
Explicación
En el primer caso: Solo hay una mesa que puede alojar a 4 personas. el 2do, 4to y 6to grupo son rechazados.
En el segundo caso: Hay 2 mesas que pueden alojar a 4 cada una.
