Đề bài

Trường của Adam đang trải qua một làn sóng dịch COVID mới. Để ngăn dịch tiếp tục lây lan, nhà trường quyết định xét nghiệm tất cả học sinh bằng bộ xét nghiệm kháng nguyên với mẫu nước bọt của các em.

Vì các giáo viên đã quên cách sử dụng những bộ xét nghiệm này từ lâu, Adam tình nguyện đến giúp. Cậu nhận được mẫu nước bọt của \(N\) học sinh; vì lý do riêng tư, cậu chỉ được biết các mã số từ \(0\) đến \(N-1\). Nhiệm vụ của cậu là xác định những mẫu dương tính.

Đáng tiếc, Adam nhận ra quá muộn rằng xét nghiệm lần lượt tất cả học sinh là một công việc vô cùng lâu và nhàm chán. Tuy nhiên, cậu nhận thấy mình có thể thực hiện việc xét nghiệm thông minh hơn. Nếu trộn một tập con các mẫu rồi xét nghiệm hỗn hợp đó, cậu sẽ biết tất cả các mẫu trong hỗn hợp đều âm tính hay có ít nhất một mẫu dương tính. Nhờ vậy, cậu có thể giảm số lần xét nghiệm cần thực hiện.

Mỗi mẫu có đủ nước bọt để Adam xét nghiệm bao nhiêu lần tùy ý. Hơn nữa, các phép xét nghiệm hoàn toàn chính xác, nên những lần xét nghiệm khác nhau trên cùng một mẫu không bao giờ cho kết quả khác nhau.

Trong các điều kiện đó, Adam muốn tối ưu hóa quy trình để sử dụng ít phép xét nghiệm nhất có thể. Tuy nhiên, cậu đang bận thực hiện xét nghiệm, nên việc tối ưu hóa được giao cho bạn.

Từ số liệu thống kê tại địa phương, Adam biết rằng xác suất để một mẫu bất kỳ dương tính là \(P\). Việc một mẫu dương tính hay âm tính không bị ảnh hưởng bởi trạng thái của bất kỳ mẫu nào khác. Có lẽ bạn có thể dùng thông tin này để tối ưu các phép xét nghiệm mà Adam thực hiện.

Giao tiếp

Đây là bài tương tác.

Chương trình của bạn sẽ được chạy trên một số bộ kiểm thử. Trong mỗi bộ kiểm thử, tức là trong một lần thực thi chương trình, bạn phải giải quyết \(T\) kịch bản khác nhau. Giá trị \(N\) và \(P\) giống nhau trong tất cả các kịch bản, nhưng những mẫu dương tính rất có thể sẽ khác nhau giữa các kịch bản.

Bạn có thể tự cài đặt giao thức bắt buộc hoặc sử dụng mã mẫu. Mã mẫu nằm trong tệp đính kèm template.cpp trên CMS.

Giao thức

Trước tiên, chương trình phải đọc một dòng từ đầu vào chuẩn chứa một số nguyên \(N\), một số thực \(P\) và một số nguyên \(T\), cách nhau bởi dấu cách, lần lượt là số học sinh, xác suất một mẫu dương tính và số kịch bản.

Sau đó, chương trình có thể ghi các truy vấn ra đầu ra chuẩn. Mỗi truy vấn là một dòng chứa Q, một dấu cách và một xâu \(s\) độ dài \(N\). Ký tự \(s_i\) là 1 nếu Adam cần thêm mẫu của học sinh thứ \(i\) vào phép xét nghiệm, và là 0 nếu không. Sau khi in dòng này, chương trình phải đẩy dữ liệu đầu ra, rồi đọc một dòng chứa một ký tự: P nếu có ít nhất một mẫu trong nhóm được xét nghiệm là dương tính, và N nếu không có mẫu nào dương tính.

Chương trình cũng có thể đưa ra câu trả lời bằng cách ghi một dòng ra đầu ra chuẩn gồm A, một dấu cách và một xâu \(s\) độ dài \(N\). Ký tự \(s_i\) là 1 nếu mẫu của học sinh thứ \(i\) dương tính, và là 0 nếu mẫu đó âm tính. Sau khi in dòng này, chương trình phải đẩy dữ liệu đầu ra, rồi đọc một dòng chứa một ký tự.

Nếu dòng nhận được chứa C, câu trả lời của bạn là đúng. Khi ấy, chương trình có thể bắt đầu truy vấn cho kịch bản tiếp theo, hoặc kết thúc nếu đây là câu trả lời thứ \(T\).

Nếu dòng nhận được chứa W, câu trả lời của bạn sai. Khi ấy, chương trình phải kết thúc ngay lập tức.

Việc kết thúc sau khi nhận W là cần thiết để CMS cung cấp phản hồi đúng. Nếu chương trình tiếp tục chạy, nó có thể gặp lỗi hoặc nhận một kết quả chấm không thành công khác.

Mã mẫu

Nếu sử dụng phần cài đặt giao thức trong template.cpp, bạn cần cài đặt hàm:

std::vector<bool> find_positive()

Hàm này được gọi đúng một lần cho mỗi kịch bản. Hàm phải trả về một vector Boolean độ dài \(N\), trong đó phần tử thứ \(i\) là true khi và chỉ khi mẫu của học sinh thứ \(i\) dương tính.

Để thực hiện việc này, bạn có thể sử dụng hàm:

bool test_students(std::vector<bool> mask)

Hàm này thực hiện một phép xét nghiệm trên một tập con các mẫu. Đối số duy nhất là một vector Boolean độ dài \(N\), trong đó phần tử thứ \(i\) là true nếu cần thêm mẫu thứ \(i\) vào hỗn hợp. Hàm trả về true khi và chỉ khi có ít nhất một mẫu trong hỗn hợp dương tính.

Bạn cũng có thể sử dụng các biến toàn cục N và P, chứa các giá trị \(N\) và \(P\) trong đề bài. Bạn có thể thực hiện mọi thao tác khởi tạo cần thiết trong hàm main sau lời gọi scanf đầu tiên.

Bộ dữ liệu

Trình chấm của bài không thích nghi, nghĩa là trạng thái dương tính của từng mẫu được xác định trước khi chương trình của bạn chạy. Hơn nữa, mỗi mẫu được xác định là dương tính một cách độc lập với xác suất \(P\), bằng một bộ sinh số ngẫu nhiên công bằng.

Chấm điểm

Có hai subtask.

• Subtask 1 (10 điểm): \(N=1\,000\), \(T=1\) và \(0\le P\le 1\). Lời giải được chấp nhận nếu trả lời đúng và sử dụng không quá \(2\cdot N\) truy vấn trên mọi bộ kiểm thử.
• Subtask 2 (90 điểm): \(N=1\,000\), \(T=300\) và \(0.001\le P\le 0.2\). Subtask này được chấm điểm thành phần theo mô tả dưới đây.

Nếu câu trả lời ở bất kỳ kịch bản nào sai, bạn nhận \(0\) điểm. Nếu tất cả câu trả lời đều đúng, điểm của một bộ kiểm thử được xác định dựa trên số truy vấn trung bình trên mỗi kịch bản; nhìn chung, số truy vấn càng ít thì điểm càng cao.

Gọi \(Q\) là số truy vấn trung bình mà chương trình sử dụng trên tất cả các kịch bản, được làm tròn xuống đến một chữ số sau dấu thập phân. Với mỗi bộ kiểm thử, ban tổ chức đã tính một giá trị \(F\) theo bảng bên dưới. Điểm trên bộ kiểm thử đó được tính như sau:

• Nếu \(Q>10\cdot F\), bạn nhận \(0\) điểm và kết quả là Wrong Answer.
• Nếu \(F<Q\le 10\cdot F\), số điểm là

• Nếu \(Q\le F\), bạn nhận đủ \(90\) điểm.

Lời giải được chấm trên nhiều bộ kiểm thử với các giá trị \(P\) khác nhau. Tổng điểm bạn nhận được là điểm nhỏ nhất trong tất cả các bộ kiểm thử, tức là trên tất cả các xác suất \(P\).

Các bộ kiểm thử như sau:

Hệ thống chấm sẽ cung cấp phản hồi cho từng bộ kiểm thử. Với mỗi bộ kiểm thử mà lời giải nhận được số điểm khác \(0\), phản hồi sẽ bao gồm giá trị \(Q\) của lời giải trên bộ đó.

Ví dụ tương tác

Dưới đây là một ví dụ tương tác với trình chấm. Lưu ý rằng các giá trị \(N\) và \(T\) trong ví dụ không thể xuất hiện trong bất kỳ subtask nào. Đừng quên đẩy dữ liệu đầu ra sau mỗi dòng.

Chương trình đã giải đúng kịch bản đầu tiên nhưng sai ở kịch bản thứ hai, vì câu trả lời đúng là 1100010010. Chương trình không thể biết câu trả lời này vì không thực hiện truy vấn nào. Kể cả khi vẫn còn một kịch bản khác, chương trình cũng phải kết thúc ngay lập tức.