Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
II Copa UHEnded |
C - Cola del pan
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Como todos sabemos, Pánfilo es un gran fanático del pan y de las colas.
Todos los días lo primero que él hace por las mañanas es intentar organizar la compra del preciado producto en el mercado próximo a su casa.La razón de tanto empeño es que en los últimos tiempos muchas de las personas se estaban molestando demasiado por las largas esperas que tenían que soportar y es que ya era practica de varios, en el momento de su turno, entablar largas conversaciones con el vendedor sobre cuanta historia circulara por el barrio.
Cuando Pánfilo llega al mercado hay $N$ personas en la cola. De cada una se conocen dos valores $t_i$ y $a_i$, que indican respectivamente el tiempo que demora hacer la compra y la molestia que le genera esperar por unidad de tiempo. Pánfilo organiza las $N$ personas y luego, durante la espera por el dependiente, suceden $Q$ eventos.
Los eventos son de dos tipos posibles:
1 - La llegada a la cola de una persona con valores $(t, a)$.
2 - La salida de la cola de la $k$-ésima persona, que aburrida de esperar decide irse a su casa.
Cada vez que ocurre un evento, Pánfilo reorganiza la cola, minimizando siempre la molestia total. La molestia total de una cola, es la suma de las molestias individuales de las personas en la cola ($a_i$ multiplicado por el tiempo consumido por las $i - 1$ personas ubicadas antes que $i$). Si diferentes colas existen con valor mínimo de molestias, Pánfilo prefiere ubicar primero aquella persona que arribó primero a la cola.
Escriba un programa que dado las caracteristicas de las $N$ personas iniciales y los $Q$ eventos, determine los valores de molestia de las colas generadas.
Input
Línea 2 ... N+1 : La $(i+1)$-ésima línea contendrá dos enteros separados por un espacio $t_i$ y $a_i$ $(1 \leq t_i, a_i \leq 10^4)$ describiendo las características de la i-ésima persona.
Línea N+2...N+Q+1 : La $(N+i+1)$-ésima línea describirá el $i$-ésimo evento. Lo primero en la línea es un caracter $w$ representando el tipo de evento, Si $w=I$ entonces siguen dos enteros $t$ y $a$ representando una persona nueva que llega a la cola. Si $w=O$, entonces sigue un entero $k$, indicando que la $k$-ésima persona actualmente en la cola organizada por Pánfilo se retira. Se garantiza que la cantidad de personas es al menos $k$ $(1 \leq k)$ cuando una persona se retira de la cola.
Output
Sample test(s)
Hints
Hint
Cuando Pánfilo llega al mercado, hay 5 personas esperando. Él organiza la cola inicial de la siguiente manera:
$(1, 5) (1, 4) (3, 6) (7, 8)$
Si esta cola fuera atendida sin interrupciones, la molestia total sería: $4 * 1 + 6 * (1 + 1) + 8 * (1 + 1 + 3) = 56$. Note que la primera persona no se molesta porque es atendida inmediatamente, la segunda persona debe esperar a la primera.
Luego, ocurre el evento O 1 indicando que la primera persona en la cola organizada se va a su casa. La nueva cola es:
$(1, 4) (3, 6) (7, 8)$
Molestia Total : $6 * 1 + 8 * (1 + 3) = 38$
Luego, ocurre el evento I 5 6 , esto significa que una nueva persona con t = 5 y a = 6 llega a la cola. La nueva cola sería:
$(1, 4) (3, 6) (5, 6) (7, 8)$
Molestia Total : $6 * 1 + 6 * (1 + 3) + 8 * (1 + 3 + 5) = 10$
Luego, ocurre el evento O 4 , indicando que la cuarta persona sale de la cola. La nueva cola sería:
$(1, 4) (3, 6) (5, 6) $
Molestia Total : $6 * 1 + 6 * (1 + 3) = 30$