/**
* I essentially screwed up this problem during contest, making me only capable of a
* bronze. Anyway, my first solution was to add at most 1 insect of each insect type to the
* machine, so we can find the total num of types & a representative of each type. Then, we
* can iterate through each repr, each time clearing the machine, then adding all insects
* of the same type to the machine. As a result, we find the cardinality of each type in
* n^2 calls. (I should've done better...)
*
* After the contest, I realized we can turn this into a decision problem. We wanna know
* about the following predicate P(bound):
* Does every insect type has cardinality >= bound?
* Therefore, the final answer equals the max bound s.t. P(bound) is true. This can be done
* with binary search. Most importantly, P(bound) can be found (quite easily) as follows:
* Iterate through all insects. First, add them to the machine. We can then
* check whether max_cardinality_in_machine <= bound (if not, just pop it).
* Consequently, every insect type has cardinality_in_machine <= bound after we
* consider every insect, so we just have to check if the num of insects in the
* machine is exactly #insect_types * bound.
* This means m is at most ~11 (log_2(n)).
*
* We now optimize the above approach. If P(bound) is true, the bound * #insect_type
* insects currently in the machine can be discarded for later consideration, because we
* know min_cardinality >= bound. Similarly, when P(bound) is false, we know
* min_cardinality < bound, so we can forget the bound-th, (bound+1)-th, (bound+2)-th, ...
* insects of any insect types can be discarded. Therefore, each time we reduce n by a
* certain amount, which means our method of choosing bound each time is critical.
*
* I was stuck for a while. Then, I noticed that when #insect_types is small, e.g. 1,
* bound shall be O(n). (Like our original binary search, and n + n/2 + n/4 + ... ~= 2n.)
* Though when #insect_types is O(n), e.g. n/2 or n, starting with n/2 may not reduce n at
* all! To sum up, when the insects are distributed evenly, bound should start small; when
* the insects are more concentrated in some types, bound should be rather "bigger". The
* sol I found was to choose bound s.t. bound * #insect_types is O(n) (e.g. n/2, 2n/3), so
* that n is always reduced by some const factor. However, I don't have a good analysis on
* m, but I guessed it's at most ~4, because every a less than 2b/3 has a multiple in
* [b/3,2b/3], though integer rounding may spoil everything. Hmmm...
*
* P.S. floor(floor(a/b)/c) = floor(a/b/c); the same holds for ceil()'s
*
* Max calls to the 3 operations: idk
* Implementation 1 (condition: 3 < m <= 6)
*/
#include <bits/stdc++.h>
#include "insects.h"
typedef std::vector<int> vec;
inline int div_ceil(int a, int b) { return (a + b - 1) / b; }
int find_bound(int n, int insect_types) {
int b1 = n / 2 / insect_types, b2 = div_ceil(div_ceil(n, 2), insect_types);
return (rand() & 1 ? b1 : b2); // Add some randomization
}
int min_cardinality(int N) {
std::vector<bool> out(N, false); // out of our consideration
int insect_types = 0;
for (int k = 0; k < N; k++) {
move_inside(k);
if (press_button() > 1)
move_outside(k);
else
insect_types++, out[k] = true;
}
for (int k = 0; k < N; k++) {
if (out[k])
move_outside(k); // clear the machine
}
// std::cerr << "[debug] types: " << insect_types << std::endl;
int base = 1, n = N - insect_types;
while (n >= insect_types) {
int bound = find_bound(n, insect_types), count = 0;
vec over, below;
for (int k = 0; k < N; k++) {
if (out[k])
continue;
move_inside(k);
if (press_button() > bound) {
move_outside(k);
over.push_back(k);
} else {
count++;
below.push_back(k);
}
}
assert(count <= bound * insect_types);
if (count == bound * insect_types) {
base += bound;
for (int b : below)
out[b] = true, n--;
} else {
for (int o : over)
out[o] = true, n--;
}
for (int b : below)
move_outside(b);
}
return base;
}
