/* https://ioi2022.id/data/editorial.pdf */ #include "insects.h" const int N = 2000; char type[N]; int min_cardinality(int n) { int d = 0; for (int i = 0; i < n; i++) { move_inside(i), type[i] = 1, d++; if (press_button() > 1) move_outside(i), type[i] = 0, d--; } int lower = 1, upper = n / d + 1, k = d; while (upper - lower > 1) { int c = (lower + upper) / 2; for (int i = 0; i < n; i++) if (type[i] == 0) { if (k + n - i < c * d) break; move_inside(i), type[i] = -1, k++; if (press_button() > c) move_outside(i), type[i] = -2, k--; if (k == c * d) break; } if (k == c * d) { lower = c; for (int i = 0; i < n; i++) if (type[i] == -1) type[i] = 1; else if (type[i] == -2) type[i] = 0; } else { upper = c; for (int i = 0; i < n; i++) if (type[i] == -1) move_outside(i), type[i] = 0, k--; } } return lower; }