A new virus has appeared in country X, with a population
of
million people.
This time the country is prepared, and wants to start tracking
its spread as quickly as possible. It is currently only known
that at least
and at
most
people are infected, and your job is to provide a more accurate
estimate on the number of infected people.
While it will take some time until tests get into mass
production, one of the research labs is able to perform up to
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 of the
actual number of infected people.
Interaction
Your program can run up to tests, and must then produce an
estimate of the number of infected people. To issue a test,
output “test ” for an integer . The judge will
then provide a line which contains either “1” if the test for randomly chosen people came back
positive, or “0” if it came back
negative. The 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 ”, where is your estimate on
the number of infected people. The answer will be treated as
correct if it is within a factor of the correct answer , i.e., if .
There will be a total of runs of your program. You may
assume that each run is deterministic: making the same sequence
of tests on the 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
infected
people based on the four tests performed.)
Read |
Sample
Interaction 1 |
Write |