Подразделы

Другие разделы

Дата и время

28/09/2022 07:19:09

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи заочного тура личного первенства 2011

printA. Поле чудес

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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 баллов. Остальные решения получают оценку, пропорциональную достигнутым результатам по сравнению с лучшим решением.
Рекомендуемая литература: Рассказ Э. По "Золотой жук"

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

Ограничения: время – 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