E. Эквивалентные состояния
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим конечный автомат с алфавитом {0, 1}.
Два его состояния называются эквивалентными,
если для любой строки `α` результаты ее обработки, начиная
с указанных состояний, совпадают. Напомним, что результатом обработки
строки может быть ее допуск или недопуск автоматом.
Для заданного конечного автомата и набора пар состояний определите,
какие из пар являются эквивалентными. Если пара состояний
не является эквивалентной, то требуется также определить
кратчайшую строку `α`, которая их различает.
Первая строка входного файла содержит число `n` — количество
состояний автомата (`1\ ≤\ n\ ≤\ 350`).
Вторая строка содержит число `t` —
количество допускающих состояний автомата и `t` чисел —
номера допускающих состояний.
Следующие `n` строк содержат по два числа, `i`-я из этих
строк содержит номера состояний, в которые автомат переходит
из состояния `i` по 0 и 1, соответственно.
Следующая строка содержит число `m` — количество запросов
`(1\ ≤\ m\ ≤\ 1000)`.
Затем следует `m` строк с запросами, каждый запрос представляет
собой пару номеров состояний.
Для каждого запроса выведите в выходной файл слово "equivalent",
если состояния являются эквивалентными, в противном случае
выведите кратчайшую строку из 0 и 1, которая их различает.
Пример ввода
5
1 5
3 5
4 5
3 3
4 4
5 5
4
1 1
3 5
1 2
1 3
Пример вывода
equivalent
equivalent
1
Источник: http://neerc.ifmo.ru/school/archive/