Google Code Jam 2021 - Hacked Exam
Xem PDFMột kỳ thi có \(Q\) câu đúng/sai; đáp án đúng mỗi câu là T hoặc F. Mỗi thí sinh chọn một trong hai cho từng câu, và điểm là số câu trả lời đúng.
Đã có \(N\) thí sinh làm bài. Bạn biết câu trả lời từng câu và điểm cuối của mỗi người. Giả sử mọi chuỗi đáp án đúng phù hợp với toàn bộ điểm của các thí sinh có xác suất bằng nhau, bạn muốn tối đa hóa điểm kỳ vọng của mình. Hãy xác định điểm kỳ vọng đó và cách trả lời để đạt được nó.
Dữ liệu vào
Dòng đầu chứa \(T\). Dòng đầu mỗi bộ chứa \(N,Q\). Mỗi trong \(N\) dòng tiếp theo chứa xâu \(A_i\) và số nguyên \(S_i\): câu trả lời và điểm của thí sinh \(i\). Ký tự thứ \(j\) của \(A_i\) là T hoặc F.
Dữ liệu ra
Với mỗi bộ, in Case #x: y z/w, trong đó \(y\) là một chuỗi đáp án đạt điểm kỳ vọng lớn nhất, còn \(z/w\) là điểm kỳ vọng cực đại dưới dạng phân số tối giản; \(w\) phải dương và nhỏ nhất có thể.
Ràng buộc
- \(1\le T\le2021\); \(|A_i|=Q\); mọi ký tự là
ThoặcF. - \(0\le S_i\le Q\); tồn tại ít nhất một chuỗi đáp án đúng phù hợp đầu vào.
Phân nhóm
- Test Set 1 (Visible Verdict): \(1\le N\le2\), \(1\le Q\le10\).
- Test Set 2 (Hidden Verdict): \(1\le N\le2\), \(1\le Q\le40\).
- Test Set 3 (Hidden Verdict): \(1\le N\le3\), \(1\le Q\le120\).
Đ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 | 8/39 | 20,51% |
| Test Set 2 | 6/39 | 15,39% |
| Test Set 3 | 25/39 | 64,1% |
Ví dụ
Ví dụ 1
Input
4
1 3
FFT 3
1 3
FFT 2
2 6
FFTTTF 2
FTFTFT 4
2 2
FF 1
TT 1Output
Case #1: FFT 3/1
Case #2: FFT 2/1
Case #3: FTFFFT 4/1
Case #4: TF 1/1Note
- Mẫu #1: điểm của
FFTlà \(3\), nên đáp án đúng buộc làFFT. - Mẫu #2: đáp án đúng là
FFF,FTThoặcTFT, mỗi chuỗi xác suất \(1/3\). TrảFFTcho kỳ vọng \((2+2+2)/3=2\). - Mẫu #3 còn có đáp án đạt kỳ vọng \(4\), chẳng hạn
FTFTFT. - Mẫu #4 có một câu
T, một câuFnhưng không biết thứ tự.TF/FTđược \(2\) với xác suất \(1/2\), \(0\) với xác suất \(1/2\);FF/TTluôn được \(1\). Mọi chuỗi có cùng kỳ vọng nên in bất kỳ.
Mẫu bổ sung Test Set 3 (không chạy trên lời giải nộp):
Input bổ sung:
1
3 120
FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFFFTFTFFTTFTFFTFFTTTFTFTFFTFTFTTFFFFTFTFFFFTTTFTTFTTTTFFFTTFFFFFTTFFTFFTFFTTTFFFFTTFFTFTTF 55
FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTTTFTTTTFFTFTTTFTTFFTTTFTFFFFTFFTTFFTTFTTFFTFTFFTFTTFTFTFFTTTFFTFTFTTFFTFTFTFTTFFTFFFTFTFT 62
FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFTFFTTTTTTFFFTTTFFFTTFTFFFFFFTFTTFFTFTTTFTTTTFTTFFFFTFFTTFTFFTTTTTTFTFFFFFTTFFTFTFTFFTTTTT 64Output bổ sung:
Case #1: FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTTTFTTTTFFTFTTTTTFFFTFTFTFFFFTFFTTFTFTFTTTTTFFTFFFFFFFFTTFTTTTTTFTTTTFFFFTFTFTTFTFFFFTTTFT 189154508532118369075350624633/2901503505434414233388602018Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).
Nguồn
Google Code Jam 2021, Vòng 1A, bài Hacked Exam.
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 2021 - Round 1A (10 Tháng tư, 2021)
Bình luận