Este es el tipo de problemas más sencillos. Aquellos en los que el propio enunciado del mismo te da el algoritmo para solucionarlos.
Sólo voy a dar un pequeño truco que empleo cuando tengo que ordenar algo por varios criterios de tal forma que se van empleando los sucesivos cuando los anteriores son iguales: convierto todos los valores del criterio en un único número y así simplifico la comparación.
Por ejemplo, en el caso del ranking de los jugadores se van a ordenar por su porcentaje de tiro en primer lugar y por su altura en el segundo. Construiré un número con ambas cantidades en los que las cifras de más valor de este número se correspondan con el criterio principal de la comparación (porcentaje de disparo) y las de menos valor con la altura. Como el rango de la altura tiene 3 cifras multiplico el porcentaje de tiro por 1000 y sumo ambas cantidades. Es fácil ver que ahora con una sola comparación puedo ordenar los jugadores.
Como en todos los problemas nuestro programa comienza con la lectura del número de casos a resolver y un bucle externo para estos casos:
cin >> T;
for (t=1; t<=T; t++)
{
}
Y ahora, para cada caso, realizaremos los siguientes pasos: lectura de datos del problema, ordenar los jugadores en los dos equipos, simular los minutos del partido realizando los cambios, ordenar alfabéticamente los nombres de los jugadores que estén en juego al final del tiempo del partido y escribir los resultados.
Lectura de datos. Definimos un struct para guardar los datos de cada jugador y creamos un array de variables de este tipo. Como adelanté en vez de guardar los dos datos para calcular el ranking de un jugador los voy a condensar en uno solo.
struct
{
char name[25];
long rank;
} students[30];
Y la lectura efectiva de los datos:
cin >> N >> M >> P; // lectura datos
for (n=0; n<N; n++)
{
long shot,height;
cin >> students[n].name >> shot >> height;
students[n].rank=shot*1000+height;
}
Para ordenar los jugadores en los dos equipos, como siempre en programación y como no me cansaré de repetir, lo primero que necesitamos es una estructura de datos que representen a los jugadores de los equipos:
struct
{
int nstudent;
long timeplay;
bool play;
} teams[2][15];
El primer campo es el vínculo al array de los datos de los jugadores anterior, el segundo acumulará el tiempo que lleva en juego y el tercero un booleano que indica si el jugador está en el campo o en el banquillo. Es un array bidimensional para separar los datos de los equipos.
Este array lo rellenaremos usando el bien conocido médodo de la burbuja, ya empleado en otros problemas (descrito en esta entrada del blog):
for (n=1, tm=0, p=0; n<=N; n++) // ordenar en equipos
{
long maxrank=0;
int stmax=0;
for (int i=0; i<N; i++)
{
if (students[i].rank>maxrank)
{
maxrank=students[i].rank;
stmax=i;
}
}
teams[tm][p].nstudent=stmax;
teams[tm][p].timeplay=n;
teams[tm][p].play=(p<P);
students[stmax].rank=0;
np[tm]=p+1;
if (++tm>1) // siguiente puesto en equipos
{
p++; tm=0;
}
}
En realidad no es una burbuja puesto que no vamos cambiando el orden de los elementos del array en el que están guardados los datos. Lo que hacemos es buscar el máximo valor en la tabla, guardar el índice del jugador en el array que representa a los equipos y guardar cero en el valor rank del jugador para que ya no vuelva a salir al buscar el máximo de la tabla porque todos los valores rank son estrictamente mayores de cero.
A parte de la variable n que controla la longitud del bucle necesitamos otras dos porque tenemos que ir guardando los valores uno en cada equipo. Lo controlamos con los índices tm y p que evolucionan con la comparación del final de bucle.
Si el jugador es elegido, dentro de su equipo, en un orden menor que el número de jugadores que juegan a la vez (P) la variable play mostrará que están en juego (true).
Finalmente en el campo de la estructura destinada a guardar el tiempo de juego guardo el número de orden en el que se ha elegido el jugados (n). ¿Por qué? Por la misma razón que en la ordenación de los jugadores. En vez del tiempo añado en la parte baja del número el número de orden de selección y el tiempo multiplicado por 100. Así, en caso de empate a tiempo de juego se me ordenarán por el número de orden de selección y nuevamente la comparación se simplifica.
Simulamos el tiempo de juego con un bucle:
for (m=0; m<M; m++) // rotaciones
{
for (tm=0; tm<2; tm++) // por equipo
if (np[tm]>P) // hay banquillo
{
long maxtime=0, mintime=100000;
int npmax=0, npmin=0;
for (n=0; n<np[tm]; n++) // buscar cambio
{
if (teams[tm][n].play) // esta jugando
{
teams[tm][n].timeplay+=100; // tiempo de juego
if (teams[tm][n].timeplay>maxtime)
{
maxtime=teams[tm][n].timeplay;
npmax=n;
}
}
else // esta en banquillo
{
if (teams[tm][n].timeplay<mintime)
{
mintime=teams[tm][n].timeplay;
npmin=n;
}
}
}
teams[tm][npmax].play=false; // cambio
teams[tm][npmin].play=true;
}
}
Por cada minuto de juego necesitaremos un bucle para hacer los cambios en los dos equipos.
Si el número de jugadores de un equipo, guardado en el array np, no es mayor que el número de jugadores que juegan a la vez no hay que hacer cambios. De ahí la primera instrucción del bucle.
Finalmente un bucle que recorre todos los jugadores del equipo. Buscaremos el que tenga el máximo valor de timeplay para los jugadores que estén en juego, a los que incrementaremos en 100 este valor para indicar que han jugado 1 minuto más, y el mínimo de entre los que están en el banquillo. Al final del bucle haremos el cambio que sólo supone cambiar de estado el campo play de los jugadores afectados.
Ya se ha terminado el partido. Ahora cogemos los nombres de los jugadores que han quedado en el campo y los ordenamos alfabéticamente:
vector<int> nstplay; // Lista ordenada de jugadores en juego
vector<int>::iterator it;
for (tm=0; tm<2; tm++)
for (n=0; n<np[tm]; n++)
if (teams[tm][n].play)
{
for (it=nstplay.begin(); it!=nstplay.end(); ++it)
if (strcmp(students[*it].name, students[teams[tm][n].nstudent].name)>0)
{
nstplay.insert(it, teams[tm][n].nstudent);
break;
}
if (it==nstplay.end())
nstplay.push_back(teams[tm][n].nstudent);
}
Otro método de ordenar elementos es partir de cero e ir añadiendo los elementos en una lista ordenándolos conforme los añadimos. Para ello partimos con una lista vacía y vamos añadiendo los elementos a ordenar. Al insertar un nuevo elemento, buscamos en la lista de los elementos ya añadidos el primero que es posterior al que se inserta en este momento y se inserta justo antes de éste. Si es posterior a todos los elementos de la lista se añade al final. Cuando se terminan de añadir los elementos, obviamente, en la lista quedan ordenados.
Recorro, con dos bucles anidados, a los jugadores de los dos equipos e inserto en un vector el número del jugador si está en el campo de juego según el algoritmo descrito en el párrafo anterior.
La clase vector, que ya hemos empleado con anterioridad (ver entrada), no es la más eficaz, pese a tener métodos para realizar las acciones de insertar y añadir al final, porque al insertar elementos en mitad de la lista mueve físicamente los elementos una posición hacia abajo, al fin y al cabo no deja de ser un array. Como el número de elementos es pequeño podemos permitirnos este lujo de ineficiencia y emplear una clase que, al poder trabajar con ella como si fuera un array, hace nuestro programa más amigable.
Para recorrer el vector, aunque se podría recorrer por su índice, empleamos un iterator, que es un índice a una posición en el vector. Los métodos begin y end del vector devuelven el primer elemento del vector y una posición después del último elemento del vector.
La variable iterator funciona como un puntero del tipo del elemento guardado en el vector, así que el operador * nos devuelve el valor del elemento al que apunta el iterator.
Todo el trabajo está hecho, sólo queda escribir el resultado:
cout << "Case #" << t << ":";
for (it=nstplay.begin(); it!=nstplay.end(); ++it)
cout << " " << students[*it].name;
cout << endl;
No hay nada que comentar de este código. Como siempre aquí os dejo el programa completo y el fichero de datos de entrada del concurso.
Estos dos fueron los únicos problemas de esta fase que me dio tiempo a realizar (como siempre montones de cosas por hacer que quitan el tiempo de estos pequeños pasatiempos). Me facilitaron el paso a la siguiente fase en la posición 2369. Aquí me podéis ver en la clasificación de la ronda.
Estos dos fueron los únicos problemas de esta fase que me dio tiempo a realizar (como siempre montones de cosas por hacer que quitan el tiempo de estos pequeños pasatiempos). Me facilitaron el paso a la siguiente fase en la posición 2369. Aquí me podéis ver en la clasificación de la ronda.
No hay comentarios:
Publicar un comentario