Условие

Программирование расширенных иерархических машин состояний – перспективная парадигма для программирования устройств, взаимодействующих с реальным миром. Иерархичность заключается в возможности вкладывать состояния друг в друга, и если входящее сообщение не обработано текущим состоянием, оно передаётся в очередное родительское состояние до тех пор, пока сообщение не будет передано на самый верхний уровень. Расширенность проявляется в возможности описывать не только граф состояний, но и непосредственно действия, а также условия-ограничения на переходы.

Но здесь мы отложим расширенность в сторону и обратимся к недетерминированным машинам состояний. В них один и тот же входящий сигнал вместо одного конкретного перехода может выполнить один из нескольких, выбранный случайным образом.

Рассмотрим недетерминированную иерархическая машину состояний (НИМС). Переход осуществляется по одному из трёх входящих сигналов (0, 1 и 2), и для каждого перехода указывается вероятность выполнить переход по его ребру. Вероятности учитываются в пределах одного состояния и их сумма может быть не равна 1. В случае, если сумма больше – вероятность перенормируется по сумме (значения вероятностей становятся весами), если меньше – имеет место необработка сигнала в текущем состоянии. Выполнение НИМС начинается с состояния под номером 0.

Ваша задача – реализовать статистический анализатор НИМС, который обрабатывает сигналы и выводит вектор вероятностей нахождения в каждом из состояний.

Формат входных данных

Проверочная система первой строкой передаёт два целых числа через пробел – количество состояний N и переходов M.

Далее система передаёт информацию о вложенности состояний в виде трёх элементов через пробел: знак `@`, далее номер родительского состояния, номер вложенного состояния. Информация не упорядочена.

Затем система передаёт M строк с информацией о переходах в виде четырёх элементов через пробел: номера входящего и исходящего состояний, номер сигнала, вероятность перехода (число от 0 до 1).

После этого проверочная система передаёт команды (каждая в одну строку) и ожидает ответ.

Передача сигнала: единственное целое число – передаваемый сигнал.

Статистика: вопросительный знак.

Завершение: амперсанд.

Формат выходных данных

Передача сигнала: одна строка со словом `OK`.

Завершение: одна строка со словом `OK`, программа должна завершиться.

Проверка координаты: одна строка с N вещественными числами через пробел – вероятности нахождения исполнителя в соответствующем состоянии.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

 

 

Last modified: Wednesday, 4 February 2026, 9:28 AM