Google Code Jam 2016 - Red Tape Committee
Xem PDFBạn là trưởng Ban Giảm Trùng lặp và Thu gọn Dư thừa. Hiện tại, ban không thể thống nhất liệu chính ban có quá nhiều “thủ tục rườm rà” (sự kém hiệu quả) hay không. Họ yêu cầu bạn thành lập một Ủy ban Thủ tục để biểu quyết vấn đề này.
Ban có \(N\) thành viên. Với mỗi người, bạn biết xác suất \(P_i\) người đó bỏ phiếu “Có”. Nếu không bỏ “Có”, họ chắc chắn bỏ “Không”; không ai bỏ phiếu trắng.
Bạn phải chọn đúng \(K\) thành viên vào ủy ban. Quy định của ban bắt buộc \(K\) là số chẵn để cho phép kết quả hòa, vốn được coi là một phần của bộ máy quan liêu lành mạnh.
Nếu chọn thành viên để tối đa hóa xác suất hòa, xác suất đó là bao nhiêu?
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N,K\), là quy mô của ban và của ủy ban. Dòng thứ hai chứa \(N\) số thập phân \(P_i\); mỗi số có đúng hai chữ số sau dấu thập phân và là xác suất thành viên thứ \(i\) bỏ phiếu “Có”.
Dữ liệu ra
Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số thực: xác suất hòa lớn nhất có thể. y được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá \(10^{-6}\).
Ràng buộc
- \(1\le T\le100\).
- \(2\le K\le N\).
- \(K\) là số chẵn.
- \(0.00\le P_i\le1.00\) với mọi \(i\).
Phân nhóm
- Test Set 1 (Hiển thị): \(2\le N\le16\).
- Test Set 2 (Ẩn): \(2\le N\le200\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 5/22 | 22,73% |
| Test Set 2 | 17/22 | 77,27% |
Ví dụ
Ví dụ 1
Input
3
2 2
0.50 0.50
4 2
0.00 0.00 1.00 1.00
3 2
0.75 1.00 0.50Output
Case #1: 0.5
Case #2: 1.0
Case #3: 0.5Giải thích
Trong bộ test số 1, bạn buộc phải dùng hai thành viên duy nhất. Ủy ban chỉ hòa khi hai người bỏ phiếu khác nhau, điều xảy ra một nửa số lần. Không mất tính tổng quát, hãy cố định phiếu của người thứ nhất; xác suất người thứ hai bỏ ngược lại là 0.5.
Trong bộ test số 2, tốt nhất là chọn một người có xác suất “Có” bằng 0.00 và một người có xác suất bằng 1.00. Điều này bảo đảm hòa.
Trong bộ test số 3, giả sử chọn hai người có xác suất “Có” là 0.50 và 0.75. Hòa xảy ra nếu người thứ nhất bỏ “Có”, người thứ hai bỏ “Không”, xác suất \(0.5\cdot0.25=0.125\); hoặc người thứ nhất bỏ “Không”, người thứ hai bỏ “Có”, xác suất \(0.5\cdot0.75=0.375\). Tổng là \(0.125+0.375=0.5\). Chọn cặp 0.50 và 1.00 cũng cho xác suất hòa 0.5, vì người 1.00 chắc chắn bỏ “Có” và người 0.50 phải bỏ “Không”. Chọn 0.75 và 1.00 chỉ cho xác suất 0.25. Vì vậy 0.5 là tốt nhất.
Nguồn
Google Code Jam 2016, Vòng 2, bài Red Tape Committee.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2016 - Round 2 (28 Tháng năm, 2016)
Bình luận