Học Máy (Bronze)

Đ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ò hiện có, mỗi con có cân nặng phân biệt và được gán nhãn có đốm (S) hoặc không có đốm (NS). Cho một dãy con bò mới với cân nặng từ $A$ đến $B$ (bao gồm cả hai đầu), hãy phân loại từng con bò mới bằng thuật toán k-nearest neighbor với $k = 1$ :

Tìm con bò hiện có có cân nặng gần nhất với con bò mới.
Nếu có một con duy nhất gần nhất: phân loại theo nhãn của con đó.
Nếu có hai con cùng khoảng cách gần nhất: phân loại là có đốm nếu ít nhất một trong hai có đốm.

Đếm số con bò mới (với cân nặng nguyên trong $[A, B]$ ) được phân loại là có đốm.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N$ , $A$ , $B$ .

$N$ dòng tiếp theo, mỗi dòng có dạng S W hoặc NS W — nhãn và cân nặng của con bò thứ $i$ .

Dữ liệu ra

Một số nguyên duy nhất — số con bò mới được phân loại là có đốm.

Ràng buộc

$1 \leq N \leq 50 000$
$1 \leq A \leq B \leq 10^{9}$
$1 \leq W_{i} \leq 10^{9}$ , các cân nặng hiện có là phân biệt

Ví dụ

Input	Output	Giải thích
3 1 10 S 10 NS 4 S 1	6	Con bò mới cân nặng 1–2 gần con bò có đốm (cân 1) nhất → có đốm. Cân 3–6 gần con bò NS (cân 4) → không. Cân 7 là điểm giữa cân 4 và 10 → có đốm (vì cân 10 có đốm). Cân 8–10 gần con bò có đốm (cân 10) → có đốm. Tổng: {1,2,7,8,9,10} = 6 con.
2 1 10 S 2 NS 8	5	Cân 1–4 gần cân 2 (có đốm) → có đốm. Cân 5 là điểm giữa cân 2 và 8 → có đốm (vì cân 2 có đốm). Cân 6–10 gần cân 8 (không đốm) → không. Tổng: {1,2,3,4,5} = 5 con.

Bình luận

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