Đại Bác

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie nhảy dọc theo một trục số có $N$ vị trí (đánh số từ $1$ đến $N$ ). Cô ấy bắt đầu tại vị trí $S$ với sức mạnh ban đầu là $1$ , di chuyển sang phải.

Mỗi vị trí là một bàn nhảy hoặc một mục tiêu, với một giá trị nguyên $v$ :

Bàn nhảy ( $q = 0$ , giá trị $v$ ): tăng sức mạnh thêm $v$ và đổi hướng di chuyển.
Mục tiêu ( $q = 1$ , giá trị $v$ ): nếu sức mạnh hiện tại $\geq v$ , mục tiêu bị phá hủy. Không thay đổi sức mạnh hay hướng di chuyển.

Bessie di chuyển bằng cách nhảy một khoảng bằng sức mạnh hiện tại theo hướng di chuyển hiện tại. Mục tiêu đã bị phá hủy vẫn tồn tại nhưng không bị phá hủy lại.

Hãy đếm số mục tiêu Bessie phá hủy trước khi rời khỏi trục số hoặc nhảy vô hạn.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $S$ ( $1 \leq N \leq 10^{5}$ , $1 \leq S \leq N$ ) - số vị trí và vị trí bắt đầu.
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $q_{i}$ và $v_{i}$ ( $q_{i} \in {0, 1}$ , $0 \leq v_{i} \leq N$ ) - loại và giá trị của vị trí thứ $i$ .

Dữ liệu ra

In một số nguyên duy nhất - số lượng mục tiêu bị phá hủy.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq S \leq N$

Ví dụ

Input	Output	Giải thích
5 2 0 1 1 1 1 2 0 1 1 1	1	Bessie phá hủy mục tiêu tại vị trí 2 (sức mạnh 1 $\geq$ 1). Nhảy sang vị trí 3 (không đủ sức), vị trí 4 (bàn nhảy, sức mạnh thành 2, đổi hướng), nhảy về vị trí 2 (đã phá), rồi ra khỏi trục.
6 4 0 3 1 1 1 2 1 1 0 1 1 1	3	Bessie phá 3 mục tiêu tại vị trí 4, 3, và 6.

Bình luận

Không có bình luận tại thời điểm này.