Problem G
Infection Estimation
While it will take some time until tests get into mass production, one of the research labs is able to perform up to $50$ tests per day. To improve test efficiency, the researchers have decided to combine tests from multiple people. Each test takes in tissue samples from any chosen number of people, and gets a positive result if there is virus in at least one of them, otherwise a negative result. The tests are performed sequentially – the result of each test becomes available before the next test can be performed.
Write a program which decides how to perform the tests and provides an estimate of the number of infected people which is within a factor $2$ of the actual number of infected people.
Interaction
Your program can run up to $50$ tests, and must then produce an estimate of the number of infected people. To issue a test, output “test $k$” for an integer $1 \le k \le 10^7$. The judge will then provide a line which contains either “1” if the test for $k$ randomly chosen people came back positive, or “0” if it came back negative. The $k$ people will be chosen without replacement, i.e., the same person cannot be chosen twice. However, the tests are independent, so a person may end up being chosen in more than one round.
To provide the estimate, output “estimate $x$”, where $0 \le x \le 10^7$ is your estimate on the number of infected people. The answer will be treated as correct if it is within a factor $2$ of the correct answer $y$, i.e., if $y/2 \le x \le 2y$.
There will be a total of $100$ runs of your program. You may assume that each run is deterministic: making the same sequence of tests on the $i$th run will always result in the same sequence of test results. To facilitate testing of your solutions, we provide a simple tool that you can download from the Kattis page for this problem. Remember to flush your standard output buffer for every line you output!
(Note: the sample interaction below is shown only for the purpose of illustrating the interaction protocol: there is no way the solution could reliably conclude the given estimate of $250\, 000$ infected people based on the four tests performed.)
| Read | Sample Interaction 1 | Write |
|---|
test 20
1
test 20
0
test 23
0
test 22
1
estimate 250000
