- Ejercicio Round-robin Queue
- Presentaciones
- Mejores Presentaciones
Round-robin Queue
Hay "n" procesos en una cola. Cada proceso tiene un nombre y un tiempo de ejecución. El planificador round-robin atiende los procesos en el orden de la cola, asignando a cada uno un quantum (intervalo de tiempo). Si un proceso no termina dentro de su quantum, se interrumpe y se mueve al final de la cola para ser reanudado más tarde, y el planificador pasa al siguiente proceso.
Por ejemplo, con quantum = 100 ms y la cola inicial:
- - A (150) – B (80) – C (200) – D (200)
1.Se atiende A durante 100 ms, pero como le quedan 50 ms se mueve al final:
- - B (80) – C (200) – D (200) – A (50)
2.Se atiende B durante 80 ms, finaliza en 180 ms y se elimina de la cola:
- - C (200) – D (200) – A (50)
Tu tarea es escribir un programa que simule este planificador round-robin.
Descripción de entrada:
En la primera línea se da un número entero, el número de casos de prueba.
En cada caso de prueba nos dan:
- - En la primera línea se dan dos enteros separados por un espacio: n - número de procesos (1 ≤ n ≤ 100 000), q: quantum en milisegundos (1 ≤ q ≤ 1000)
- - En las siguientes "n" líneas se describen los procesos, uno por línea: name[i]: cadena de longitud entre 1 y 10 caracteres, time[i]: tiempo de ejecución en milisegundos (1 ≤ time[i] ≤ 50 000)
Además, la suma total de todos los time[i] no supera 1 000 000.
Descripción de salida:
Para cada proceso, en el orden en que finaliza, imprime su nombre y el instante de tiempo (en ms) en que termina, separados por un espacio, uno por línea.
Notas del ejercicio:
Nota de BlitzCoding:
La primera línea del INPUT siempre será un número N que indica el número de casos del problema propuesto. Para los ejemplos de este ejercicio entonces N será 2. Le siguen el número de casos.
| Entrada |
|---|
| 2 |
| 5 100 p1 150 p2 80 p3 200 p4 350 p5 20 |
| 11 10 a 10 b 20 c 5 d 12 e 30 f 9 g 20 h 100 i 10 j 20 k 10 |
| Salida | Explicación |
|---|---|
| p2 180 p5 400 p1 450 p3 550 p4 800 | |
| a 10 c 25 f 54 i 84 k 104 b 114 d 116 g 136 j 156 e 166 h 246 |