Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Data Science] KNN khoảng cách Manhattan

    Phân lớp điểm truy vấn qqq bằng K láng giềng gần nhất với khoảng cách Manhattan:

    d(x,q)=∑j=1d∣xj−qj∣d(x,q)=\sum_{j=1}^{d}|x_j-q_j|d(x,q)=∑j=1d​∣xj​−qj​∣

    Lấy kkk điểm gần nhất (nếu khoảng cách bằng nhau, ưu tiên chỉ số nhỏ hơn). Bỏ phiếu đa số trên nhãn của chúng; nếu hòa số phiếu, chọn nhãn nhỏ hơn. In nhãn dự đoán.

    • Định dạng đầu vào:

      Dòng đầu: nnn ddd kkk. Tiếp theo nnn dòng (ddd tọa độ + nhãn). Dòng cuối: ddd tọa độ của qqq.

    • Ràng buộc đầu vào:

      1≤k≤n≤10001 \le k \le n \le 10001≤k≤n≤1000; 1≤d≤101 \le d \le 101≤d≤10.

    • Định dạng đầu ra:

      Một số nguyên: nhãn dự đoán.

    Ví dụ:

    Đầu vào:

    3 1 1
0 0
5 1
6 1
1

    Đầu ra:

    0

    Giải thích:

    q=1. Khoảng cách: |0−1|=1, |5−1|=4, |6−1|=5. Gần nhất là điểm 0 (nhãn 0). k=1 → in 0

    Đang tải editor...