頁面無法載入？點擊這裡可能會修復。
Placeholder

#6214
子任務

캐논볼 1s 1024MB

問題

정올이는 길이가 N인 수직선에서 포탄으로 변신하여 튕겨 나가는 기술을 익혔습니다. 수직선의 위치는 1, 2, ..., N으로 번호가 매겨져 있습니다. 정올이는 정수 위치 S에서 시작하여 오른쪽으로 튕기며, 시작 힘은 1입니다. 만약 정올이의 힘이 k라면, 다음 튕김은 현재 위치에서 k만큼 앞으로 이동합니다.

모든 정수 위치 1부터 N까지에는 목표물이 있거나 점프 패드가 있습니다.

  • 각 목표물과 점프 패드는 0부터 N까지의 정수 값 v를 가집니다.

  • 점프 패드의 값 v는 정올이의 힘을 v만큼 증가시키고 방향을 반전시킵니다.

  • 목표물의 값 v는 최소한 v의 힘으로 착지하면 파괴됩니다. 목표물에 착지하는 것은 정올이의 힘이나 방향을 변화시키지 않습니다. 파괴된 목표물은 계속해서 파괴된 상태로 남아 있으며, 정올이는 그 위에 튕길 수 있습니다.

정올이가 무한한 시간 동안 튕기거나 수직선을 벗어날 때까지 튕길 경우, 몇 개의 목표물을 파괴할까요?

정올이가 파괴할 수 있는 목표물 위에서 시작하는 경우, 즉시 파괴합니다. 마찬가지로 정올이가 점프 패드 위에서 시작하는 경우, 첫 번째 점프 전에 패드의 효과가 적용됩니다.


輸入

첫 번째 줄에는 N과 S가 주어집니다. 여기서 N은 수직선의 길이이고, S는 정올이의 시작 위치입니다.

다음 N줄에는 각 위치를 설명하는 정보가 포함되어 있습니다.

i번째 줄에는 두 개의 정수 q_i와 v_i가 있습니다. 여기서 q_i = 0이면 위치 i에는 점프 패드가 있고, q_i = 1이면 위치 i에는 목표물이 있으며, v_i는 위치 i에 있는 오브젝트의 값입니다.

[제약 조건]

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


輸出

파괴된 목표물의 수를 나타내는 정수 하나를 출력합니다.


子任務

編號 分數 條件
#133分

N \le 100

#233分

N \le 1000

#334分

추가 제약 조건 없음


範例 #1

5 2
0 1
1 1
1 2
0 1
1 1
1

정올이는 위치 2에서 시작하는데, 이는 값이 1인 목표물입니다. 따라서 즉시 파괴합니다. 이후 위치 3으로 튕기는데, 이는 값이 2인 목표물로, 파괴할 수 없습니다. 그 후 위치 4로 튕기고, 여기서 방향이 반전되며 힘이 1 증가하여 2가 됩니다. 정올이는 다시 위치 2로 튕기지만 이미 파괴된 목표물 위에 착지하므로 계속 진행합니다. 이 시점에서 위치 0으로 튕기게 되어 멈추게 됩니다. 결국 위치 2에서 한 개의 목표물만 파괴하게 됩니다.


範例 #2

6 4
0 3
1 1
1 2
1 1
0 1
1 1
3

정올이의 경로는 4 -> 5 -> 3 -> 1 -> 6이며, 다음 튕김은 수직선을 벗어나게 됩니다 (11). 정올이는 순서대로 목표물 4, 3, 6을 파괴합니다.



來源

USACO 2024 January Bronze

需要登入才能撰寫程式碼。