Birthday paradox giải thích vì sao va chạm hàm băm xảy ra sớm hơn trực giác. Với n phần tử gán ngẫu nhiên vào d giá trị, xác suất có ít nhất một cặp trùng là:
P = 1 - ∏_{i=0}^{n-1} (d - i)/d
Nếu n > d thì chắc chắn trùng (P = 1).
Đọc n và d (cách nhau khoảng trắng), in P với 6 chữ số thập phân.
Input:
23 365
Output:
0.507297
Một dòng: hai số nguyên n và d.
0 ≤ n ≤ 100000. 1 ≤ d ≤ 10^9.
Một dòng: xác suất, 6 chữ số thập phân.
Ví dụ:
Đầu vào:
23 365
Đầu ra:
0.507297
Giải thích:
Đang tải editor...