Chạy Bộ (Silver)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $N$ con bò chạy bộ trên đường thẳng vô hạn, mỗi con có vị trí xuất phát phân biệt và vận tốc riêng. Khi một con bò nhanh đuổi kịp con bò chậm phía trước, nó phải giảm tốc và cùng chạy theo nhóm. Sau $T$ phút, hãy đếm số nhóm còn lại.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $T$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_{i}$ và $s_{i}$ — vị trí và vận tốc của con bò thứ $i$ . Các con bò được cho theo thứ tự tăng dần vị trí.

Dữ liệu ra

Một số nguyên duy nhất — số nhóm sau $T$ phút.

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq T \leq 10^{9}$
$0 \leq p_{i}, s_{i} \leq 10^{9}$ , các vị trí phân biệt và tăng dần

Ví dụ

Input	Output	Giải thích
5 3 0 1 1 2 2 3 3 2 6 1	3	Sau 3 phút: nhóm {0}, {1}, {2,3,4} (tọa độ chiếu lần lượt: 3, 7, 9). Vị trí chiếu của các con bò: 3, 7, 11, 9, 9.
10 0 10 5 15 46 18 87 37 33 45 60 60 14 73 71 78 65 80 2 96 5	10	T=0, chưa có nhóm nào hình thành, mỗi con bò là một nhóm riêng.

Bình luận

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