Cannonball.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Bessie ha aprendido el arte de rebotar a lo largo de una recta numérica de longitud N con posiciones numeradas 1, 2, \ldots, N de izquierda a derecha. Ella comienza en alguna posición entera S rebotando a la derecha con una potencia inicial de 1. Si Bessie tiene potencia k, su siguiente rebote será a una distancia k hacia adelante desde su posición actual.

Cada posición entera de 1 a N es o un objetivo o una almohadilla de rebote. Cada objetivo y almohadilla de rebote tiene un valor entero en el rango 0 a N inclusive. Una almohadilla de rebote con un valor de v aumenta la potencia de Bessie en v y cambia su dirección. Un objetivo con un valor de v se romperá si se aterriza con una potencia de al menos v. 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 N y S, donde S es la longitud de la recta numérica y S es la posición inicial de Bessie.

Cada una de las N líneas siguientes describen cada una de las posiciones. La i-ésima de esas líneas contiene los enteros, q_i y v_i, donde q_i=0 si la posición i es una almohadilla de rebote y q_i=1 si la posición i es un objetivo, y donde v_i es el valor de la posición i

Salida

Dé como salida un número representando el número de objetivos que se romperán.

Restricciones

  • 1 \leq N \leq 10^5
  • 1 \leq S \leq N

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 4 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 6, donde el siguiente rebote la llevaría afuera de la recta numérica (11). Ella rompe los objetivos 4,3,6 en ese orden.

Calificación

Entradas Puntos Restricción
3–5 3 N \leq 100
6–10 5 N \le 1000
11–20 10 Sin restricciones adicionales

USACO 2024 January Contest, Bronze Problem 2. Cannonball.


Comments

There are no comments at the moment.