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

    solution

    Đề bài: [Data Science] KNN trọng số nghịch đảo khoảng cách

    KNN có trọng số: mỗi láng giềng đóng góp một phiếu tỉ lệ nghịch với khoảng cách Euclid tới qqq. Lấy kkk láng giềng gần nhất (hòa khoảng cách → chỉ số nhỏ hơn). Trọng số của láng giềng iii là wi=1/diw_i=1/d_iwi​=1/di​ (nếu di=0d_i=0di​=0 coi như trọng số rất lớn 101210^{12}1012). Tổng trọng số theo từng lớp; chọn lớp có tổng trọng số lớn nhất (hòa → lớp nhỏ hơn). In nhãn dự đoán.

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

      Dòng đầu: nnn ddd kkk KKK (số lớp). Tiếp theo nnn dòng (ddd tọa độ + nhãn). Dòng cuối: ddd tọ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ãn ∈{0,…,K−1}\in\{0,\dots,K-1\}∈{0,…,K−1}.

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

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

    Ví dụ:

    Đầu vào:

    3 1 3 2
0 0
2 0
3 1
0

    Đầu ra:

    0

    Giải thích:

    q=0. dist: 0,2,3. w: lớp0 nhận 1/0→10¹² (điểm0) cộng 1/2 (điểm1)=lớn; lớp1 nhận 1/3. Lớp0 lớn nhất → in 0

    Đang tải editor...