printРабочее место участника

printЗадачи

1670. Радиоактивность

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Есть `N` шаров, из них `M` шаров радиоактивные. В детектор можно загрузить от 1 до `N` шаров. Детектор подает сигнал, если среди них окажется `K` или более радиоактивных. Необходимо найти радиоактивные шары, сделав как можно меньше испытаний.
Вы должны написать подпрограмму с именем solve.
void solve(int n, int m, int k, int a[]); // C/C++

type flags=array[1..100] of boolean;
procedure solve(n,m,k:integer;var a:flags); // Pascal
Этой подпрограмме передается общее количество шаров `N`, количество радиоактивных шаров `M`, порог срабатывания детектора `K` (`1\ ≤\ K\ ≤\ M\ <\ N\ ≤\ 100`), и массив флагов, в котором после выхода из подпрограммы должны быть отмечены радиоактивные шары (`a_i\ =\ 1`, если `i`-й шар – радиоактивный).
Для проверки набора шаров подпрограмма должна вызывать функцию check.
int check(int a[]); // C/C++
function check(var a:flags):boolean; // Pascal
В качестве аргумента необходимо передать массив флагов (`a_i\ =\ 1`, если `i`-й шар нужно поместить в детектор). Функция возвращает истину, если в заданном наборе будет не менее `K` радиоактивных.
Пересылаемое на проверку решение должно содержать только подпрограмму solve, вспомогательные функции, команды #include (в C/C++) и глобальные переменные. В функциях не должен выполняться ввод или вывод.
Решение участника, которое находит радиоактивные шары за минимальное количество испытаний, получает оценку 100 баллов. Решение, которое находит радиоактивные шары за `2*N` или более испытаний, получает оценку 0 баллов. Остальные решения получают оценку, пропорциональную достигнутым результатам по сравнению с лучшим решением.
В 50% тестов `1\ ≤\ K\ =\ M\ <\ N\ ≤\ 100`, в остальных тестах `1\ ≤\ K\ <\ M\ <\ N\ ≤\ 100`.
loading