Начало
Соревнования
Задачи заочного тура личного первенства 2011
A. Поле чудес
Интерактивные задачиОлимпиадные задачи на русском языке
Эвристические и приближенные методы
| 01/09/2011 | Заочный тур личного первенства (A) |
| 21/11/2013 | Занятие 10 для продолжающих (E) |
Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Загадано некоторое английское слово, случайно выбранное из словаря.
Слово содержит от 1 до 20 букв. Первоначально все буквы слова заменены символом '*'.
Можно назвать одну из 26 букв алфавита от 'a' до 'z' и все буквы слова, совпадающие с названной, будут открыты.
Необходимо, сделав как можно меньшее количество попыток, открыть все буквы слова.
Вы должны написать подпрограмму с именем solve, угадывающую загаданное слово.
void solve(const char s[]); // С/С++ procedure solve(var s:string); // Pascal
Этой подпрограмме передается строка, первоначально состоящая из символов '*'. Количество символов '*' в строке совпадает с длиной загаданного слова.
По мере угадывания символы '*' в строке будут заменяться на буквы.
Для угадывания буквы подпрограмма должна вызывать функцию guess.
int guess(char b); // С/С++ function guess(b:char):integer; // Pascal
В качестве аргумента необходимо указать строчную английскую букву от 'a' до 'z'. Функция возвращает количество открытых букв.
Пересылаемое на проверку решение должно содержать только подпрограмму solve,
вспомогательные функции, команды #include (в C/C++) и глобальные переменные.
В функциях не должен выполняться ввод или вывод.
Пример программы на С/C++
void solve(const char s[])
{ char ch;
for(ch='a';ch<='z';++ch)
{ guess(ch);
if(strchr(s,'*')==NULL) break;
}
}
Пример программы на Pascal
procedure solve(var s:string);
var ch:char;
begin
for ch:='a' to 'z' do
begin
guess(ch);
if pos('*',s)=0 then break;
end;
end;
Решение участника, которое открывает слово за минимальное количество попыток,
получает оценку 100 баллов. Решение, которое открывает слово за количество попыток,
большее или равное, чем у решения, приведенное в примере,
получает оценку 0 баллов. Остальные решения получают оценку, пропорциональную достигнутым результатам
по сравнению с лучшим решением.
Рекомендуемая литература:
Рассказ Э. По "Золотой жук"
B. Радиоактивность
Интерактивные задачиОлимпиадные задачи на русском языке
Эвристические и приближенные методы
| 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`.
