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

    solution

    Đề bài: [Xác suất - Thống kê] Truy vết nguồn hạt giống lỗi

    Một kho nông sản nhập hạt giống từ nnn nông trại. Nông trại thứ iii đóng góp tỷ lệ pip_ipi​ trong tổng số hạt giống của kho (pi≥0p_i \ge 0pi​≥0, ∑i=1npi=1\sum_{i=1}^n p_i = 1∑i=1n​pi​=1), và có tỷ lệ hạt lỗi (không nảy mầm) là did_idi​ (0≤di≤10 \le d_i \le 10≤di​≤1).

    Lấy ngẫu nhiên một hạt giống từ kho và phát hiện nó bị lỗi. Theo định lý Bayes, xác suất hậu nghiệm hạt giống này đến từ nông trại iii là:

    P(noˆng trại i∣loˆ˜i)=pidi∑j=1npjdjP(\text{nông trại } i \mid \text{lỗi}) = \frac{p_i d_i}{\sum_{j=1}^n p_j d_j}P(noˆng trại i∣loˆ˜i)=∑j=1n​pj​dj​pi​di​​

    Hãy tìm nông trại có xác suất hậu nghiệm lớn nhất (nghi ngờ nhiều nhất là nguồn gốc). Nếu có nhiều nông trại đồng hạng cao nhất, chọn nông trại có chỉ số nhỏ nhất.

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

      Dòng đầu chứa số nguyên nnn (1≤n≤10001 \le n \le 10001≤n≤1000). nnn dòng tiếp theo, mỗi dòng chứa hai số thực pip_ipi​ và did_idi​ (tối đa 6 chữ số thập phân), cách nhau bởi khoảng trắng, theo thứ tự nông trại 1,2,…,n1, 2, \dots, n1,2,…,n.

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

      Nếu tồn tại nông trại với xác suất hậu nghiệm dương lớn nhất: in ra một dòng gồm hai giá trị cách nhau bởi khoảng trắng — chỉ số nông trại (1-based) và xác suất hậu nghiệm tương ứng làm tròn 6 chữ số thập phân (ví dụ 3 0.666667). Nếu ∑pidi=0\sum p_i d_i = 0∑pi​di​=0 (không thể quan sát hạt lỗi), in ra UNDEFINED.

    Ví dụ:

    Đầu vào:

    2
    0.5 0.1
    0.5 0.1
    

    Đầu ra:

    1 0.500000
    

    Đầu vào:

    1
    0.5 0.02
    

    Đầu ra:

    1 1.000000
    

    Đang tải editor...