Planificación de professores y asignaturas X84909
La entrada de este ejercicio tendrá una o más lineas, donde cada una especifica una clase que se imparte durante la semana. Más concretamente, una linea tiene un nombre de asignatura, un nombre de profesor, un dia de la semana, una hora de inicio y una hora de final. Por ejemplo:
algebra joel monday 8 10 physics guille thursday 10 14 programming guille thursday 11 13 programming nuria thursday 12 14 statistics silvia tuesday 9 10 deeplearning silvia tuesday 8 10
Para simplificar, los nombres de asignaturas y profesores son strings de letras minúsculas. Los dias de la semana siempre son uno de {monday,tuesday,wednesday,thursday,friday}. Las dos horas h1,h2 siempre cumplen h1<h2 i están en el conjunto {0,…,24}.
Como podéis ver en el ejemplo anterior, puede haber repeticiones de asignatura y conflictos de profesores (una asignatura se puede estar dando más de una vez simultaneamente, y un profesor puede estar asignado a más de una clase simultaneamente).
La primera parte de la salida tendrá una descripción en forma de tabla de cuantas clases se dan en cada hora de la semana. La primera columna (h) tiene anchura 2 y es para describir la hora de inicio. Las siguientes 5 columnas tienen anchura 10 cada una y son para cada dia de la semana. Todas las columnas están justificadas a la derecha. Cada fila muestra la información de una hora en concreto. Solo se muestran horas desde la primera en que comienza alguna clase hasta la última en la que todavía se estará dando alguna clase. Este sería el resultado correspondiente al ejemplo anterior:
number of subjects per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 2 0 0 0 10 0 0 0 1 0 11 0 0 0 2 0 12 0 0 0 3 0 13 0 0 0 2 0
En una segunda parte de la salida tenemos una tabla con el mismo formato, pero ahora cada celda muestra el número de profesores diferentes que están impartiendo clase durante aquella hora y dia (es decir, el número de profesores que imparten durante aquella hora y dia después de haber eliminado repeticiones). Este sería el resultado correspondiente al ejemplo anterior:
number of teachers per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 1 0 0 0 10 0 0 0 1 0 11 0 0 0 1 0 12 0 0 0 2 0 13 0 0 0 2 0
Finalmente, la salida tiene un natural, que es el mínimo número de horas de clase donde necesitamos reemplazar al profesor actual por algún profesor nuevo con el fin de que no hayan conflictos, es decir, para conseguir que ningún profesor esté impartiendo dos clases simultaneamente. Este sería el resultado correspondiente al ejemplo anterior:
number of replacements needed to avoid conflicts: 3
Para resolver este ejercicio, es obligatorio que uséis convenientemente las siguientes estructuras de datos. En caso contrario, se invalidará la entrega.
struct Slot {
vector<string> listsubjects;
vector<string> listteachers;
};
typedef vector<vector<Slot> > TableSlots;
Entrada
La entrada ya se ha descrito en el propio enunciado del problema. Hechad una ojeada a los juegos de pruebas públicos para terminar de ver los detalles.
Salida
La salida ya se ha descrito en el propio enunciado del problema. Hechad una ojeada a los juegos de pruebas públicos para terminar de ver los detalles.
Observación
Evaluación sobre 10 puntos:
- Solución lenta: 5 puntos.
- Solución rápida: 10 puntos.
Entendemos como solución rápida una que es correcta, de coste nlog(n) y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.
Input
algebra joel monday 8 10 physics guille thursday 10 14 programming guille thursday 11 13 programming nuria thursday 12 14 statistics silvia tuesday 9 10 deeplearning silvia tuesday 8 10
Output
number of subjects per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 2 0 0 0 10 0 0 0 1 0 11 0 0 0 2 0 12 0 0 0 3 0 13 0 0 0 2 0 number of teachers per slot: h monday tuesday wednesday thursday friday 8 1 1 0 0 0 9 1 1 0 0 0 10 0 0 0 1 0 11 0 0 0 1 0 12 0 0 0 2 0 13 0 0 0 2 0 number of replacements needed to avoid conflicts: 3
Input
algebra jose wednesday 19 23 analysis jose wednesday 9 11 history sonia monday 19 23 analysis nuria tuesday 4 6 programming merce wednesday 21 24 biology guille thursday 19 20 physics jordi wednesday 18 23 music laia tuesday 19 22 analysis manel tuesday 23 24 biology merce friday 11 12 analysis jose tuesday 20 22 geometry guille monday 4 6 philosphy nuria friday 15 17 music jose friday 1 4 pedagogy nuria wednesday 9 14 biology angels friday 3 4 history manel tuesday 2 6 geometry manel tuesday 2 7 philosphy nuria tuesday 0 5 biology jose tuesday 6 11 analysis oscar friday 10 13 physics guille wednesday 21 24 physics ferran tuesday 8 10 botanics nuria friday 4 9 pedagogy serge tuesday 13 16 analysis sandra monday 21 24 algebra jose wednesday 9 11 pedagogy jose thursday 11 16 algebra sandra wednesday 5 9 music nuria thursday 4 5 biology serge tuesday 11 15 computers ferran tuesday 1 2 analysis laia friday 20 22 physics laia monday 2 7 history joel wednesday 8 12 pedagogy guille monday 3 5 pedagogy ferran wednesday 4 5 physics serge tuesday 2 3 philosphy sonia monday 1 5 computers manel tuesday 0 5 algebra joel thursday 19 23 philosphy ferran monday 16 20 analysis manel friday 21 24 analysis angels thursday 6 10 physics angels wednesday 5 10 botanics laura friday 2 4 computers guille wednesday 8 11 geometry nuria friday 20 22 music manel friday 15 17 history oscar wednesday 23 24 music jose tuesday 18 22 computers nuria tuesday 4 6 biology laura thursday 16 19 pedagogy angels wednesday 6 11 botanics sandra wednesday 11 16 arts merce tuesday 21 23 arts oscar thursday 14 15 history joel tuesday 11 13 analysis manel thursday 12 13 geometry ferran tuesday 20 21 programming angels tuesday 6 8 geometry nuria tuesday 19 23 botanics guille thursday 4 9 programming ferran monday 6 9 physics sandra thursday 12 14 philosphy angels friday 9 14 philosphy jose monday 11 12 geometry guille monday 0 4 algebra joel wednesday 5 7 physics nuria friday 4 7 history laura monday 9 12 analysis oscar wednesday 2 6 pedagogy laura friday 14 19 geometry serge tuesday 12 13 computers joel friday 17 21 analysis nuria monday 4 7 biology joel thursday 13 15 computers angels thursday 1 6 programming serge friday 10 13 analysis angels tuesday 18 22 programming joel wednesday 12 16 pedagogy sandra thursday 1 5 programming laia thursday 8 9 history sonia tuesday 8 13 botanics sandra thursday 5 10 computers laia thursday 3 6 pedagogy sonia tuesday 21 24 pedagogy oscar thursday 21 24 arts nuria friday 9 10 analysis merce wednesday 2 6 analysis guille friday 9 14 history angels wednesday 12 16 physics ferran wednesday 18 23 physics laura friday 19 22 programming jordi friday 5 10 physics laura friday 23 24 analysis oscar thursday 11 16 history guille thursday 12 13 algebra serge friday 22 24 botanics sandra friday 2 5
Output
number of subjects per slot: h monday tuesday wednesday thursday friday 0 1 2 0 0 0 1 2 3 0 2 1 2 3 5 2 2 3 3 4 4 2 3 4 4 5 6 3 5 3 5 3 4 5 4 3 6 3 3 4 3 3 7 1 2 3 3 2 8 1 3 5 4 2 9 1 3 7 2 4 10 1 2 6 0 4 11 2 3 3 2 5 12 0 4 4 5 4 13 0 2 4 4 2 14 0 2 3 4 1 15 0 1 3 2 3 16 1 0 0 1 3 17 1 0 0 1 2 18 1 2 2 1 2 19 2 4 3 2 2 20 1 6 3 1 4 21 2 7 5 2 4 22 2 3 5 2 2 23 1 2 3 1 3 number of teachers per slot: h monday tuesday wednesday thursday friday 0 1 2 0 0 0 1 2 3 0 2 1 2 3 3 2 2 3 3 3 2 2 3 4 4 4 2 3 5 2 5 3 2 5 4 2 6 3 3 3 3 2 7 1 2 2 3 2 8 1 3 4 4 2 9 1 3 5 2 4 10 1 2 5 0 4 11 2 3 3 2 5 12 0 3 4 5 4 13 0 1 4 4 2 14 0 1 3 3 1 15 0 1 3 2 3 16 1 0 0 1 3 17 1 0 0 1 2 18 1 2 2 1 2 19 2 4 3 2 2 20 1 5 3 1 4 21 2 6 5 2 4 22 2 3 5 2 2 23 1 2 3 1 3 number of replacements needed to avoid conflicts: 27