Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1670. Радиоактивность
Интерактивные задачиОлимпиадные задачи на русском языке
Эвристические и приближенные методы
| 01/09/2011 | Заочный тур личного первенства (B) |
Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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`.
