Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Вдоль длинной улицы расположены дома (хотя бы два), в каждом из которых живёт по одному человеку. Каждый из жителей улицы является сторонником одной из двух политических партий: 1 или 2. Каждый день каждый человек общается со всеми своими соседями (с одним соседом, если человек живёт в на краю улицы и с обоими соседями в остальных случаях). За ночь он обдумывает полученную от них информацию, и если оказывается, что двое его соседей являются сторонниками противоположной политической партии, к утру человек меняет свои взгляды.
На вход подаётся произвольная последовательность единиц и двоек, соответствующая политическим взглядам жителей улицы в какой-то из дней. Последовательность заканчивается символом f. Постройте схему, которая преобразует которая преобразует эту строку в строку, соответствующую политическим взглядам жителей улицы на следующий день, начинающуюся символом s. Например, строка 12121f должна превратиться в s11211.
Данная схема состоит из вершин (называемых состояниями) и стрелок. Каждая стрелка соединяет два состояния и символизирует переход схемы из первого состояния во второе.. Схема начинает работу в начальном состоянии S0, выделенном оранжевым. Поступающее на вход слово анализируется посимвольно. При анализе каждого символа схема переходит из текущего состояния по стрелке, над которой написан этот символ. При этом символ, написанный над стрелкой через пробел, подаётся на выход.
S2 - состояние, где предыдущие две цифры были 1 и 1, S3 - где предыдущие две цифры были 1 и 2, S4 - где предыдущие две цифры были 2 и 1, S5 - где предыдущие две цифры были 2 и 2. Выход из каждого такого состояния однозначно определяет цифру, которую нужно поставить и следующее состояние, расставляем стрелки между состояниями соответствующим образом. Буква f ведет в финальное состояние, последняя цифра однозначно определяется предыдущим состоянием.