Ошибка.
Попробуйте повторить позже
На вход устройства подается лента с записанными на ней нулями и единицами:
За один такт устройство считывает с ленты с позиций (на первом такте ) три значения . Если то устройство на новой ленте печатает 1 , иначе — 0 . Затем устройство сдвигается на одну позицию вправо, и процедура повторяется. Найдите разности и если известно, что а на новой ленте было напечатано следующее: (для примера на рисунке изображен случай
Источники:
Подсказка 1
Да, можно и перебрать d_1 и d_2, но это будет долго) Попробуем сократить перебор! Что мы вообще умеем делать? Мы умеем брать конкретные элементы ленты и считать их сумму, если расстояния между ними это d_1 и d_2. Какие "удобные" элементы хочется взять?
Подсказка 2
Рассмотрим систему неравенств, которая соответствует выходных знакам вида 1...1 на расстоянии d_1. С помощью нее мы сможем дать ограничения на элементы, находящиеся на расстоянии d_1. Таким образом мы сможем перебрать и методом "пристального взгляда на ленту" найти d_1. Аналогично с d_2!
Число возможных вариантов и , можно для каждого варианта проверять, что соответствие входных и выходных символов, а можно предложить более быстрый способ, заключающийся в нахождении сначала (максимум 10 вариантов), а затем . Для этого достаточно заметить следующее.
Если рассмотреть систему, соответствующую выходным знакам на расстоянии вида в произвольном такте работы
то если , то
Это позволяет отбраковать опробуемый вариант Устанавливаем, что
Аналогично, если рассмотреть систему, соответствующую выходным знакам на расстоянии вида в произвольном такте работы
тогда если то
Это позволяет отбраковать опробуемый вариант (с учётом найденного ранее Находим
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!