trang chủ / đề bài / icpc21_nat_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à á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 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 để xác định ai nhiễm virus.

Trong một khu vực có n gia đình, được đánh số từ 0 đến n−1. Gia đình thứ i có ai thành viên. Mỗi gia đình tạo thành một nhóm. Sau khi chạy n xét nghiệm cho n nhóm, có đúng k 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 n và k.
  • Dòng thứ hai chứa n số nguyên a0,a1,…,an−1.

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

  • 0≤k≤n≤1000.
  • 1≤ai≤10.

Ví dụ

Input Output Giải thích
5 2
2 3 4 5 6
5 11 Nếu nhóm 0 và 1 dương tính, cần thêm 5 xét nghiệm; nếu nhóm 3 và 4 dương tính, cần thêm 11 xét nghiệm.
3 1
1 2 3
0 3 Nếu nhóm 0 dương tính, không cần xét nghiệm cá nhân nào vì nhóm này chỉ có 1 thành viên.

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