Cannonball.
Bessie ha aprendido el arte de rebotar a lo largo de una recta numérica de longitud con posiciones numeradas
de izquierda a derecha. Ella comienza en alguna posición entera
rebotando a la derecha con una potencia inicial de
. Si Bessie tiene potencia
, su siguiente rebote será a una distancia
hacia adelante desde su posición actual.
Cada posición entera de a
es o un objetivo o una almohadilla de rebote. Cada objetivo y almohadilla de rebote tiene un valor entero en el rango
a
inclusive. Una almohadilla de rebote con un valor de
aumenta la potencia de Bessie en
y cambia su dirección. Un objetivo con un valor de
se
romperá si se aterriza con una potencia de al menos
. Aterrizar en un objetivo no cambia el poder de Bessie o la dirección. Un objetivo que está roto permanecerá roto y Bessie aún puede rebotar en el, también sin cambiar potencia o dirección.
Si Bessie rebota durante una cantidad infinita de tiempo o hasta que ella deje la recta numérica, ¿cuántos objetivos romperá?
Si Bessie comienza en un objetivo que ella puede romper, lo hará inmediatamente. De manera similar, si Bessie comienza en una almohadilla de salto, los efectos de la almohadilla serán aplicados antes de su primer rebote.
Entrada
La primera línea de la entrada contiene y
, donde
es la longitud de la recta numérica y
es la posición inicial de Bessie.
Cada una de las líneas siguientes describen cada una de las posiciones. La i-ésima de esas líneas contiene los enteros,
y
, donde
si la posición
es una almohadilla de rebote y
si la posición
es un objetivo, y donde
es el valor de la posición
Salida
Dé como salida un número representando el número de objetivos que se romperán.
Restricciones
Ejemplo #1 de Entrada
5 2
0 1
1 1
1 2
0 1
1 1
Ejemplo #1 de Salida
1
Bessie comienza en la coordenada 2, la cual es un objetivo de valor 1, entonces ella inmediatamente lo rompe. Ella luebo rebota a la coordenada 3, la cual es un objetivo de valor 2, entonces ella no lo puede romper. Ella continúa a la coordenada 4, la cual cambia su dirección e incremente su poder en 1 a 2. Ella rebota de vuelta a la coordenada 2, la cual es un objetivo ya roto, por lo tanto, ella continua. En este punto, ella rebota a la coordenada 0, entonces ella se detiene. Ella rompe exactamente un objetivo ubicado en 2.
Ejemplo #2 de Entrada
6 4
0 3
1 1
1 2
1 1
0 1
1 1
Ejemplo #2 de Salida
3
El camino que Bessie toma es , donde el siguiente rebote la llevaría afuera de la recta numérica (11). Ella rompe los objetivos
en ese orden.
Calificación
| Entradas | Puntos | Restricción |
|---|---|---|
| 3–5 | 3 | |
| 6–10 | 5 | |
| 11–20 | 10 | Sin restricciones adicionales |
USACO 2024 January Contest, Bronze Problem 2. Cannonball.
Comments