trang chủ / đề bài / icpc21_reg_g

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 p 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ả p 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ó n người từ nước ngoài trở về. Họ được đánh số từ 1 đến 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 1 đứng đầu hàng, người n đứ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á 2 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 10 bộ xét nghiệm. Mỗi xét nghiệm mất nhiều giờ nên ta muốn làm cả 10 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 n, rồi đưa ra một phương án gồm 10 xét nghiệm làm song song. Sau đó, chương trình nhận kết quả của cả 10 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í z nhiễm virus, chương trình phải tìm ra vị trí z.
  • Nếu có đúng hai người ở vị trí z và z+1 nhiễm virus, chương trình phải tìm ra vị trí z hoặc z+1 (cả hai đều được chấp nhận).

Tương tác

  • Đầu tiên, chương trình đọc số nguyên n: số người.
  • Tiếp theo, chương trình in ra 10 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 p (0≤p≤n): số người tham gia xét nghiệm này.
    • Tiếp theo là p số nguyên phân biệt x1,x2,…,xp (1≤xi≤n): chỉ số của những người tham gia xét nghiệm.
  • Sau đó, chương trình đọc 10 dòng là kết quả của 10 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 đủ 10 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 −1.
    • Ngược lại, in z (1≤z≤n): người ở vị trí z 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ả 10 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

  • 1≤n≤1000.

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 7 và 8 nhiễm virus: chỉ xét nghiệm 3 (có người 7, 8) và xét nghiệm 4 (có người 8) dương tính. Kết luận 8 (kết luận 7 cũng đúng). Đề gốc minh họa cùng tình huống bằng 10 xét nghiệm khác: xét nghiệm thứ i gồm người i và i+1 (xét nghiệm thứ 10 gồm người 10 và 1).
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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0