Google Code Jam 2017 - Core Training
Xem PDFViết đề Code Jam rất khó, nên chúng tôi đã xây dựng một AI để nghĩ ra ý tưởng mới. Để AI sáng tạo nhất có thể, chúng tôi cấp cho nó \(N\) “lõi” khác nhau, mỗi lõi có một “tính cách” riêng. Tuy nhiên, cũng như con người, các lõi có thể mất tập trung, bị hỏng hoặc từ chối làm việc; lõi thứ \(i\) hoạt động đúng với xác suất thành công \(P_i\). Chỉ cần ít nhất \(K\) lõi hoạt động đúng thì AI hoạt động đúng. Nếu không, nó có lẽ sẽ hóa ác và nhốt chúng tôi trong một mê cung gồm những câu đố quái ác do chính nó thiết kế. Ai biết nó sẽ làm gì với Code Jam — có khi nó chỉ viết hàng loạt bài xác suất khó nhằn!
Để ngăn điều đó, chúng tôi dự định huấn luyện một hoặc nhiều lõi cho đáng tin cậy hơn. Ta có tổng cộng \(U\) “đơn vị huấn luyện”. Dùng \(X\) đơn vị cho lõi thứ \(i\) sẽ cộng \(X\) vào xác suất thành công của lõi đó. Có thể phân chia tùy ý, kể cả không cấp đơn vị nào cho một số lõi. Dĩ nhiên, xác suất thành công của một lõi không thể vượt quá 1.
Nếu phân bổ các đơn vị huấn luyện sao cho xác suất AI hoạt động đúng là lớn nhất, xác suất đó bằng 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 ba dòng. Dòng đầu chứa hai số nguyên \(N\) và \(K\): tổng số lõi và số lõi tối thiểu phải thành công để AI hoạt động đúng. Dòng thứ hai chứa số hữu tỉ \(U\), số đơn vị huấn luyện. Dòng thứ ba chứa \(N\) số hữu tỉ \(P_i\); số thứ \(i\) là xác suất lõi thứ \(i\) hoạt động đúng. Tất cả các xác suất được cho với đúng bốn chữ số sau dấu thập phân.
Dữ liệu ra
Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là xác suất AI hoạt động đúng khi phân bổ tối ưu. y được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá \(10^{-6}\).
Ràng buộc
- \(1\le T\le100\).
- \(1\le N\le50\).
- \(0.0000\le P_i\le1.0000\) với mọi \(i\).
- \(0.0000\le U\le N-\sum_iP_i\); luôn có thể dùng hết số đơn vị huấn luyện.
Phân nhóm
Bài có hai tập nhỏ và không có tập lớn. Trong cuộc thi gốc, phải giải Test Set 1 trước khi thử Test Set 2 và có thể thử lại mỗi tập với hình phạt thời gian.
Test Set 1 (Visible): \(K=N\); mọi lõi đều phải hoạt động đúng thì AI mới hoạt động đúng.
Test Set 2 (Visible): \(1\le K\le N\).
Đ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 | 15/43 | 34,88% |
| Test Set 2 | 28/43 | 65,12% |
Ví dụ
Ví dụ 1
Input
4
4 4
1.4000
0.5000 0.7000 0.8000 0.6000
2 2
1.0000
0.0000 0.0000
2 1
0.0000
0.9000 0.8000
2 1
0.1000
0.4000 0.5000Output
Case #1: 1.000000
Case #2: 0.250000
Case #3: 0.980000
Case #4: 0.760000Giải thích
Hai test cuối không xuất hiện trong Test Set 1.
Ở test 1, số đơn vị huấn luyện đủ để nâng xác suất thành công của mọi lõi lên 1, nên AI chắc chắn hoạt động đúng.
Ở test 2, cả hai lõi đều phải thành công. Phương án tốt nhất là nâng mỗi lõi lên 0.5, cho xác suất \(0.5\times0.5=0.25\). Mọi cách khác đều kém hơn; chẳng hạn nâng một lõi lên 0.9 và lõi kia lên 0.1 chỉ cho \(0.9\times0.1=0.09\).
Ở test 3, không có đơn vị huấn luyện và chỉ cần ít nhất một trong hai lõi thành công. Xác suất cả hai cùng hỏng là \((1-0.9)(1-0.8)=0.02\), nên xác suất ít nhất một lõi thành công là \(1-0.02=0.98\).
Ở test 4, tối ưu là cấp toàn bộ đơn vị huấn luyện cho lõi thứ hai, khi đó xác suất ít nhất một lõi thành công là \(1-(0.4\times0.6)=0.76\). Cấp hết cho lõi đầu chỉ được 0.75, còn chia đều được 0.7525.
Nguồn
Google Code Jam 2017, Vòng 1C, bài Core Training.
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 2017 - Round 1C (30 Tháng tư, 2017)
Bình luận