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à áp dụng chiến lược 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 để xác định ai nhiễm virus.
Trong một khu vực có gia đình, được đánh số từ đến . Gia đình thứ có thành viên. Mỗi gia đình tạo thành một nhóm. Sau khi chạy xét nghiệm cho nhóm, có đúng nhóm cho kết quả dương tính.
Hãy tính số xét nghiệm cá nhân bổ sung ít nhất và nhiều nhất mà ta phải làm.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
In ra hai số nguyên: số xét nghiệm cá nhân bổ sung ít nhất và nhiều nhất phải làm.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 2 3 4 5 6 |
5 11 | Nếu nhóm và dương tính, cần thêm xét nghiệm; nếu nhóm và dương tính, cần thêm xét nghiệm. |
| 3 1 1 2 3 |
0 3 | Nếu nhóm dương tính, không cần xét nghiệm cá nhân nào vì nhóm này chỉ có thành viên. |
Bình luận