Cuộc Đua Bò

Đ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

Hai con bò cùng xuất phát từ một vị trí và chạy trên cùng một đường thẳng. Mỗi con chạy theo nhiều đoạn, trong mỗi đoạn tốc độ không đổi. Hãy đếm số lần thay đổi vị trí dẫn đầu — tức là số lần một con bò đang đứng sau vượt lên trước con kia.

Con bò 1 (Bessie) chạy $N$ đoạn, con bò 2 (Elsie) chạy $M$ đoạn. Hai con bò chạy trong cùng tổng thời gian. Nếu hai con đang ngang nhau rồi một con vượt lên, đây tính là một lần thay đổi dẫn đầu.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$ ( $1 \leq N, M \leq 1000$ )
$N$ dòng tiếp theo: Tốc độ $v_{i}$ và thời gian $t_{i}$ cho từng đoạn của Bessie ( $1 \leq v_{i}, t_{i} \leq 1000$ )
$M$ dòng tiếp theo: Tốc độ $v_{j}$ và thời gian $t_{j}$ cho từng đoạn của Elsie ( $1 \leq v_{j}, t_{j} \leq 1000$ )

Dữ liệu ra

Một số nguyên duy nhất: số lần thay đổi vị trí dẫn đầu.

Ràng buộc

$1 \leq N, M \leq 1000$
$1 \leq v_{i}, t_{i} \leq 1000$
Tổng thời gian chạy của hai con bò bằng nhau

Ví dụ

Input	Output	Giải thích
4 3 1 2 4 1 1 1 2 10 2 3 1 2 3 9	2	Elsie dẫn đầu đến thời điểm $t = 3$ khi hai con ngang nhau. Sau đó Bessie vượt lên (lần đổi 1), rồi Elsie vượt lại (lần đổi 2).

Bình luận

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