Xét nghiệm gộp
Đề bài
Mô tả
Trong đợt bùng phát đầu tiên của đại dịch COVID-19, xét nghiệm diện rộng trên toàn dân đã chứng tỏ là một trong những chiến lược tốt nhất để kiểm soát và ngăn chặn dịch bệnh. Tuy nhiên, xét nghiệm PCR tốn cả thời gian lẫn tiền bạc. Một cách hiệu quả để tăng tốc và tiết kiệm nguồn lực là xét nghiệm gộp.
Theo phương pháp này, thay vì xét nghiệm từng người, ta trộn mẫu của người rồi xét nghiệm một lần. Nếu kết quả âm tính, có thể kết luận chắc chắn cả người đều âm tính. Ngược lại, nếu kết quả dương tính, cần xét nghiệm từng người để biết ai nhiễm virus.
Hôm nay có người từ nước ngoài trở về. Họ được đánh số từ đến theo thứ tự xếp hàng làm xét nghiệm trước khi nhập cảnh Việt Nam: người đứng đầu hàng, người đứng cuối hàng.
Dữ liệu cho thấy những người này rất ít khả năng nhiễm virus vì họ đã xét nghiệm âm tính trước chuyến bay. Khi đến Việt Nam, có không quá người nhiễm virus. Hơn nữa, nếu có đúng hai người nhiễm virus thì họ phải đứng ở hai vị trí liên tiếp.
Khó khăn là chỉ còn đúng bộ xét nghiệm. Mỗi xét nghiệm mất nhiều giờ nên ta muốn làm cả xét nghiệm song song. Ta cần xác định có người nhiễm virus hay không, và nếu có ít nhất một người nhiễm, cần chỉ ra vị trí của đúng một người nhiễm.
Cụ thể, bạn cần viết chương trình đọc số người , rồi đưa ra một phương án gồm xét nghiệm làm song song. Sau đó, chương trình nhận kết quả của cả xét nghiệm và kết luận như sau:
- Nếu không ai nhiễm virus, chương trình phải kết luận là không có ca dương tính.
- Nếu chỉ có đúng một người ở vị trí nhiễm virus, chương trình phải tìm ra vị trí .
- Nếu có đúng hai người ở vị trí và nhiễm virus, chương trình phải tìm ra vị trí hoặc (cả hai đều được chấp nhận).
Tương tác
- Đầu tiên, chương trình đọc số nguyên : số người.
- Tiếp theo, chương trình in ra dòng, mỗi dòng mô tả một xét nghiệm theo định dạng:
- Dòng bắt đầu bằng số nguyên (): số người tham gia xét nghiệm này.
- Tiếp theo là số nguyên phân biệt (): chỉ số của những người tham gia xét nghiệm.
- Sau đó, chương trình đọc dòng là kết quả của xét nghiệm (theo đúng thứ tự đã in). Mỗi dòng là POSITIVE hoặc NEGATIVE. NEGATIVE nghĩa là mọi người tham gia xét nghiệm đó đều không nhiễm virus; POSITIVE nghĩa là có ít nhất một người tham gia nhiễm virus, nhưng không biết là bao nhiêu người hay chính xác những ai. Lưu ý rằng chương trình chỉ đọc được các dòng này sau khi đã in đủ dòng ở bước trước.
- Cuối cùng, chương trình in ra kết luận là một số nguyên:
- Nếu không ai nhiễm virus, in .
- Ngược lại, in (): người ở vị trí nhiễm virus.
- Sau đó, chương trình kết thúc.
Hãy nhớ flush đầu ra sau khi in (ví dụ cout << flush hoặc fflush(stdout) trong C++, sys.stdout.flush() hoặc print(..., flush=True) trong Python).
Vì cả xét nghiệm được chọn trước khi biết bất kỳ kết quả nào, kết luận của chương trình chỉ phụ thuộc vào các kết quả nhận được. Bài làm được chấp nhận nếu kết luận đúng với mọi tình huống (không ai nhiễm, một người nhiễm, hai người liên tiếp nhiễm) cho cùng các kết quả đó.
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 NEGATIVE NEGATIVE POSITIVE POSITIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE |
6 1 2 5 6 9 10 5 2 3 4 5 10 7 4 5 6 7 8 9 10 3 8 9 10 0 0 0 0 0 0 8 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Người và nhiễm virus: chỉ xét nghiệm (có người , ) và xét nghiệm (có người ) dương tính. Kết luận (kết luận cũng đúng). Đề gốc minh họa cùng tình huống bằng xét nghiệm khác: xét nghiệm thứ gồm người và (xét nghiệm thứ gồm người và ). |
| 3 NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE NEGATIVE |
2 1 2 2 2 3 0 0 0 0 0 0 0 0 -1 |
Ví dụ bổ sung (không có trong đề gốc). Mọi xét nghiệm đều âm tính nên không ai nhiễm virus. |
Bình luận