Начало
Соревнования
Задачи заочного тура личных соревнований 2014
A. Молодильные яблоки
Не классифицирована| 25/09/2014 | Отборочный тур личных соревнований (A) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Кащей Бессмертный решил жениться на Василисе Прекрасной. Для реализации этого плана
он выменял у Бабы-Яги волшебную яблоню, на которой через каждые `m` дней к вечеру вырастает молодильное яблоко.
На обычного человека эти яблоки оказывают продолжительный эффект, но Кащей очень стар, суперстар,
поэтому яблоко на него действует только один день.
Чтобы Василиса окончательно забыла об Иване-царевиче,
Кащею нужно ухаживать за Василисой не менее `k` дней подряд.
Первоначально у Кащея нет яблок, а до нового урожая нужно ждать `m` дней.
Определите через какое минимальное количество дней Кащей сможет приступить к осуществлению своего коварного замысла.
Формат ввода
В первой строке ввода содержатся два целых числа `k` и `m` (`1\ ≤\ k\ ≤\ 10^6`, `2\ ≤\ m\ ≤\ 10^6`).
Формат вывода
Вывести одно целое число – через сколько дней Кащей сможет начать ухаживание за Василисой.
Пример ввода
5 2
Пример вывода
6
Пояснение к примеру: через 6 дней у Кащея будет 3 яблока, когда он их будет использовать,
во 2-й день ухаживаний вечером вырастет еще одно яблоко, которое будет использовано на 4-й день,
а вечером этого дня он сорвет еще одно яблоко для 5-го дня.
В 50% тестов `k,\ m\ ≤\ 30`.
B. Случайный палиндром
Не классифицирована| 25/09/2014 | Отборочный тур личных соревнований (B) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Имеется мешок с `n` шариками, на которых написаны латинские буквы.
На каждом шарике написана одна буква.
Шарики случайным образом достаются из мешка и кладутся в ряд, пока мешок не опустеет.
Определите вероятность того, что получившееся слово будет палиндромом, то есть будет читаться
одинаковым образом слева направо и справа налево.
Формат ввода
Первая строка ввода содержит набор строчных латинских букв, написанных на шариках. Количество букв в строке от 1 до 50.
Формат вывода
Вывести вероятность с относительной погрешностью не более `10^{-10}` (рекомендуется выводить число в экспоненциальной форме).
Пример ввода
abbat
Пример вывода
6.666666667e-002
Пояснение к примеру:
из 5!=120 способов расположить 5 шариков, в 4 вариантах получится слово-палиндром "abtba" и в 4 вариантах – "batab".
Вероятность равна (4+4)/120=0.0666666667.
В 50% тестов количество букв не будет превышать 10.
C. Определение последовательности
Не классифицирована| 25/09/2014 | Отборочный тур личных соревнований (C) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Загадана последовательность из '0' и '1' длиной от 1 до 256 символов.
Можно делать запросы на наличие в этой последовательности некоторой непрерывной подпоследовательности.
Необходимо, сделав как можно меньшее количество попыток, определить всю последовательность.
Вы должны написать подпрограмму с именем solve, определяющую последовательность.
void solve(int n, char r[]); // С/С++ procedure solve(n:integer; var r:string); // Pascal
Этой подпрограмме передается длина последовательности `n` и она должна вернуть в параметре `r` найденную последовательность.
Для проверки наличия подпоследовательности подпрограмма должна вызывать функцию guess.
int guess(const char s[]); // С/С++ function guess(const s:string):boolean; // Pascal
В качестве аргумента необходимо указать подпоследовательность. Функция возвращает 1 (true), если подпоследовательность есть, иначе 0 (false).
Пересылаемое на проверку решение должно содержать только подпрограмму solve,
вспомогательные функции, команды #include (в C/C++) и глобальные переменные.
В функциях не должен выполняться ввод или вывод.
Пример программы на С/C++
#include <string>
using namespace std;
void solve(int n, char r[])
{ int i;
string s;
for(i=0;i<n;++i)
{ s+='0';
if(!guess(s.c_str()))
{
s[i]='1';
if(!guess(s.c_str()))
{ s.erase(i,1);
s="0"+s;
if(!guess(s.c_str()))
s[0]='1';
}
}
}
strcpy(r,s.c_str());
}
Пример программы на Pascal
procedure solve(n:integer; var r:string);
var i:integer;
s:string;
begin
s:='';
for i:=1 to n do
begin
s:=s+'0';
if not guess(s) then
begin
s[i]:='1';
if not guess(s) then
begin
s:='0'+copy(s,1,i-1);
if not guess(s) then
s[1]:='1';
end;
end;
end;
r:=s;
end;
Решение участника, которое открывает слово за минимальное количество попыток,
получает оценку 100 баллов. Решение, которое открывает слово за `2*n` или более попыток,
получает оценку 0 баллов. Остальные решения получают оценку, пропорциональную достигнутым результатам
по сравнению с лучшим решением.
