시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 371 | 32 | 28 | 10.938% |
Andrew the mushroom expert is investigating mushrooms native to Singapore.
As part of his research, Andrew collected $n$ mushrooms labelled $0$ to $n-1$. Each mushroom is of one of two species, which are called A and B.
Andrew knows that mushroom $0$ belongs to species A, but as the two species look the same, he does not know the species of mushrooms $1$ to $n-1$.
Fortunately, Andrew has a machine in his lab that can help with this. To use this machine, one should place two or more mushrooms in a row inside the machine (in any order) and turn the machine on. Then, the machine calculates the number of adjacent pairs of mushrooms that are of different species. For example, if you place mushrooms of species $[A,B,B,A]$ (in that order) into the machine, the result will be $2$.
However, as operating the machine is very expensive, the machine can be used for a limited number of times. In addition, the total number of mushrooms placed in the machine across all its uses cannot exceed $100\;000$. Use this machine to help Andrew count the number of mushrooms of species A collected.
You should implement the following procedure:
int count_mushrooms(int n)
The above procedure can make calls to the following procedure:
int use_machine(int[] x)
use_machine
among all its invocations cannot exceed $100\;000$.Consider a scenario in which there are $3$ mushrooms of species $[A, B, B]$, in order. The procedure count_mushrooms
is called in the following way:
count_mushrooms(3)
This procedure may call use_machine([0, 1, 2])
, which (in this scenario) returns $1$. It may then call use_machine([2, 1])
, which returns $0$.
At this point, there is sufficient information to conclude that there is only $1$ mushroom of species A. So, the procedure count_mushrooms
should return $1$.
Consider a case in which there are $4$ mushrooms with species $[A, B, A, A]$, in order. The procedure count_mushrooms
is called as below:
count_mushrooms(4)
This procedure may call use_machine([0, 2, 1, 3])
, which returns $2$. It may then call use_machine([1, 2])
, which returns $1$.
At this point, there is sufficient information to conclude that there are $3$ mushrooms of species A. Therefore, the procedure count_mushrooms
should return $3$.
If in any of the test cases, the calls to the procedure use_machine
do not conform to the rules mentioned above, or the return value of count_mushrooms
is incorrect, the score of your solution will be $0$. Otherwise, let $Q$ be the maximum number of calls to the procedure use_machine
among all test cases. Then, the score will be calculated according to the following table:
Condition | Score |
---|---|
$ 20\;000 < Q \phantom{\leq 20\;000} $ | $ 0 $ |
$ 10\;010 < Q \leq 20\;000 $ | $ 10 $ |
$ \phantom{00\;} 904 < Q \leq 10\;010 $ | $ 25 $ |
$ \phantom{00\;} 226 < Q \leq \phantom{00\;} 904 $ | $ \frac{226}{Q} \cdot 100 $ |
$ \phantom{20\;000 <} Q \leq \phantom{00\;} 226 $ | $ 100 $ |
In some test cases the behavior of the grader is adaptive. This means that in these test cases the grader does not have a fixed sequence of mushroom species. Instead, the answers given by the grader may depend on the prior calls to use_machine
. Though, it is guaranteed that the grader answers in such a way that after each interaction there is at least one sequence of mushroom species consistent with all the answers given so far.
Olympiad > International Olympiad in Informatics > IOI 2020 > Day 2 5번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)