Процессы и алгоритмы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Петя задумал слово длины 
состоящее только из букв 
и 
Вася может спросить у Пети, является ли некоторое слово 
подсловом задуманного слова, и получить честный ответ. Докажите, что Вася может гарантированно отгадать слово, придуманное Петей, за
вопросов.
Подсказка 1
Для начала попробуйте найти максимально входящую степень буквы a. За сколько вопросов это можно сделать?
Подсказка 2
Правильно! Половинным делением начиная с a⁵¹² это можно точно понять за 10 вопросов. Обозначим за d максимальную степень, а за S эту самую последовательность из a. Давайте теперь последовательно задавать вопросы Sa, Sa¹b,Sa²b ... Sa^d. Как только получаем ответ "да", меняем S на найденную строку и начинаем сначала. Что можно сказать про конец нашего слова, если все ответы на эти вопросы будут "нет"?
Подсказка 3
Верно! Тогда конец слова будет выглядеть, как Saⁿ при некотором n. Сколько вопросов нам потребуется, чтоб найти n?
Подсказка 4
Точно, n + 1 вопрос! Будем спрашивать Sa¹,Sa²... пока не получим ответ "нет". Теперь попробуйте посчитать сколько вопросов нам потребуется, чтоб узнать конец, если длина этого конца равна d + k?
Подсказка 5
Ага, d + k + 12 вопросов. Осталось понять, как можно быстро найти буквы, которые стоят до S. Попробуйте каждым вопросом узнавать хотя бы одну букву.
Шаг 
Половинным делением (начиная с 
за 
вопросов можно выяснить максимальную входящую степень буквы 
Пусть это
Обозначим 
Шаг 
Задаём последовательно вопросы 
При этом: а) если мы получили ответ да, то останавливаемся и
меняем 
на найденную строку. Мы увеличили 
на 
символов за 
вопросов. Снова запускаем шаг 
с новым 
б) Все 
ответов нет. Поскольку 
не входит в слово, это значит, что 
— конец слова при некотором 
Спрашиваем про 
пока
не получили ответ нет. Мы потратили 
вопросов, увеличили длину известного подслова на 
при этом это подслово
— конец загаданного. Итого, если длина полученного слова равна 
то мы потратили 
вопросов.
Шаг 
Теперь, если мы знаем конец 
то вопросом 
мы определяем предыдущую букву. Итого на слово длины 
потрачено
вопросов.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
