Problem Description

This problem is translated from CEOI 2024 Day 1 Task 2「COVID tests」.

A new wave of COVID has recently broken out at Adam’s school. To prevent the outbreak from spreading further, the school decided to use saliva antigen test kits to test all students.

Because the teachers have not used these kits for a long time, Adam volunteered to be a testing helper. He received saliva samples from $N$ students (for privacy reasons, he can only see identifiers numbered from $0$ to $N-1$), and his task is to determine which samples are positive.

However, Adam soon realized that testing every student one by one is too time-consuming and tiring. Then he came up with a smarter method than testing individually. If he mixes some samples together and tests them, he can tell whether the whole mixture is all negative, or whether at least one sample is positive. This way, he can reduce the number of tests needed.

Each sample has enough saliva for multiple tests. Also, these test kits are very accurate, so the same sample will never produce different test results.

Under these conditions, Adam wants to optimize the testing process and use as few tests as possible. But since he is busy testing right now, the optimization is left to you.

From local statistics, Adam knows that the probability that any given sample is positive is $P$, and whether one sample is positive or negative does not affect the test results of other samples. Maybe you can use this information to help Adam optimize the testing plan.

Input Format

This is an interactive problem.

Your program will handle multiple testdata. In each testdata (i.e., one run of your program), you need to solve $T$ different scenarios. In all scenarios, the number of students $N$ and the positive probability $P$ stay the same, but which students are positive (most likely) differs from scenario to scenario.

You may implement the interactive protocol yourself, or use the provided template. In the “Files” section you can find an attachment named template.cpp, which is the provided template.

First, your program should read one line from standard input containing three space-separated values $N, P, T$, representing the number of students, the probability of a positive sample, and the number of scenarios.

Then, your program may output queries to standard output. Each query must be on its own line, in the format Q, a space, and a string $s$ of length $N$. Each character $s_i$ is either 1 or 0. 1 means the sample of student $i$ should be added to the mixture for testing, and 0 means it should not be added. After outputting a query, your program must flush the output buffer, then read one character from standard input. This character will be P (meaning at least one sample in the mixture is positive) or N (meaning all samples in the mixture are negative).

Your program may also output a final answer. The answer must be on its own line, in the format A, a space, and a string $s$ of length $N$. Each character $s_i$ is either 1 or 0. 1 means the sample of student $i$ is positive, and 0 means it is negative. After outputting an answer, your program must also flush the output buffer, then read one character from standard input.

If the read character is C, your answer is correct. In this case, your program may start processing queries for the next scenario, or if it was the answer for the $T$-th scenario, it may exit.

If the read character is W, your answer is incorrect. Your program must exit immediately.

Note that exiting after receiving W is very important for the interactor to provide correct feedback. If your program continues running, it may crash or receive other wrong verdicts.

The interactor will not adapt the testdata based on how your program behaves. This means whether each sample is positive or negative is fixed before your program starts. Also, each sample’s status is determined independently by a fair random generator with probability $P$.

If you implement the interaction using the protocol in template.cpp, you need to implement the function std::vector<bool> find_positive(). This function is called once in each scenario. It must return a boolean vector of length $N$, where the $i$-th element is true if and only if the $i$-th student’s sample is positive.

During implementation, you may use the function bool test_students(std::vector<bool> mask). This function performs a mixed test on some samples. Its only parameter is a boolean array of length $N$, where the $i$-th element is true if the $i$-th sample should be included in the mixture. The function returns true if and only if at least one sample in the mixture is positive.

You may also use the global variables N and P, which represent the total number of students and the probability of a positive sample. You may initialize them in main after the first call to scanf.

Hint

This problem has two subtasks.

Subtask 1 (10 points)

• Total number of students $N = 1000$.
• Number of scenarios $T = 1$.
• Positive probability $P$ is between $0$ and $1$.

If the program always answers correctly and the number of queries in each testdata does not exceed $2$ times the total number of students $2N$, then the program passes.

Subtask 2 (90 points)

• Total number of students $N = 1000$.
• Number of scenarios $T = 300$.
• Positive probability $P$ is between $0.001$ and $0.2$.

This subtask has partial scoring.

If your program gives a wrong answer in any scenario, you will get $0$ points. Otherwise, the score for each testdata is based on the average number of queries. In general, fewer queries give a higher score. Let $Q$ be the average number of queries over all scenarios, rounded to one digit after the decimal point. For each testdata, we compute a value $F$ (see below). The score for the given testdata is computed as follows:

• If $Q > 10$ times $F$, you will get $0$ points (wrong answer).
• If $F < Q \leq 10$ times $F$, the score is computed by:$$90 \cdot \frac{F}{F + 4 \cdot (Q-F)}$$
• If $Q \leq F$, you will get the full $90$ points.

Your program will be scored on testdata with different values of $P$. Your total score is the minimum score among all testdata (all probabilities $P$).

The testdata are:

The interactor will provide feedback for each testdata. This feedback will include the average number of queries $Q$ on the testdata where your score is non-zero.

Translated by ChatGPT 5