Решение: Работа редактора со строкой
Исполнитель Редактор получает на вход строку из 150 цифр, содержащую по 50 цифр 1, 2 и 3, расположенных в произвольном порядке. В цикле, пока в строке встречается хотя бы одна из цепочек 21, 31 или 32, выполняются следующие команды: если найдена цепочка 21, первое слева её вхождение заменяется на 12; если найдена цепочка 31, первое слева её вхождение заменяется на 13; если найдена цепочка 32, первое слева её вхождение заменяется на 23. Определите, какие цифры будут находиться на 10-м, 80-м и 140-м местах строки после выполнения программы. Запишите полученные цифры подряд без пробелов и разделителей.
Решение по шагам
4 шагаКаждая команда меняет местами соседнюю пару цифр, стоящих в неправильном порядке: 21, 31 или 32.
$$21\to12,\quad 31\to13,\quad 32\to23$$При каждой такой замене число инверсий в строке уменьшается. Цикл завершается только тогда, когда ни одной пары 21, 31 или 32 не осталось, то есть строка упорядочена по возрастанию.
Количество каждой цифры не изменяется: в упорядоченной строке находятся 50 единиц, затем 50 двоек и затем 50 троек.
$$1^{50}2^{50}3^{50}$$Позиция 10 находится среди первых 50 символов, позиция 80 — среди позиций с 51-й по 100-ю, а позиция 140 — среди последних 50 символов.
$$a_{10}=1,\quad a_{80}=2,\quad a_{140}=3$$Где здесь ошибаются
Ошибочно считать, что замены изменяют количество цифр.
Не учитывать, что после завершения цикла все единицы идут перед двойками, а двойки — перед тройками.
Неверно определять диапазоны позиций: 1–50, 51–100 и 101–150.