Весь курс подготовки к КЕГЭ здесь.
Условие задачи:
На ленте в соседних ячейках записана последовательность из 1000 символов,
включающая только нули и единицы. Ячейки справа и слева
от последовательности заполнены пустыми символами «λ». В начальный
момент времени головка расположена в ближайшей ячейке справа
от последовательности.
Программа работы исполнителя:
После выполнения программы на ленте осталось ровно 343 нуля.
Определите максимально возможное число нулей в исходной
последовательности.
Решение:
Итак, чтобы решить это задание, нужно уметь пользоваться логикой и анализом. Смотрим внимательно на нашу таблицу.
Представим, что наша исходная строка будет все нули, что будет в итоге? По таблице все 0 заменятся на 1 и когда мы достигнем левого края (потому что мы двигаемся влево L), то программа закончит работу (достигнем пустого символа - действие q1 и первый столбец).
Представим, что наша исходная строка состоит из единиц. Тогда после запуска программы, работа остановится, заменив самый правый символ 1 на 0.
Преставим, что где-то посередине есть 1. Тогда, начиная справа программа будет заменять нули на 1, и как только мы достигнем 1 программа остановится.
Теперь давайте на примере (возьмем короткие примеры):
- 000001000 - превратится в 000000111. 8 нулей в начале, и 6 нулей в конце.
- 00100100 - превратится в 00100011. 6 нулей в начале, и 5 нулей в конце.
Делаем вывод, что, чтобы осталось 343 нуля (остальные 1), нам нужно поставить 342 нуля в начале и 1 после них. И если учесть, что программа работает до ближайшей справа 1, то после 1 тоже ставим нули. Получается следующая строка:
- 000..00 - 342 штуки
- 1 - 1 штука
- 000..00 - 657 штук (1000 - 343)
Итоговый вид: 000...00100...00. В итоге (то есть начальная строка имеет 999 нулей).
Ответ:
999
Мое решение на Python есть в публикациях.