Имя входного файла: problem1.in
Имя выходного файла: problem1.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Задан детерминированный конечный автомат и слово. Определить, допускает ли данный ДКА заданное слово.
В первой строке входного файла находится слово, состоящее из не более чем 100000 строчных латинских букв.
Во второй строке содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно. ( 1 ≤ n; m ≤ 100000 , 1 ≤ k ≤ n ).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния прону- мерованы от 1 до n ).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b— номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Требуется выдать строку "Accepts", если автомат принимает заданное слово, или "Rejects" в противном случае.
problem1.in
abacaba
2 3 1
2
1 2 a
2 1 b
2 1 c
problem1.out
Accepts
Имя входного файла: problem2.in
Имя выходного файла: problem2.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Задан недетерминированный конечный автомат и слово. Определить, допускает ли данный НКА заданное слово.
В первой строке входного файла находится слово, состоящее из не более чем 10000 строчных латинских букв.
Во второй строке содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно ( 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 , 1 ≤ k ≤ n ).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход. Стартовое состояние автомата всегда имеет номер 1.
Требуется выдать строку "Accepts", если автомат принимает заданное слово, или "Rejects" в противном случае.
problem2.in
abacaba
4 6 1
2
1 2 a
2 1 c
2 3 b
3 2 a
2 4 b
1 4 a
problem2.out
Accepts
Имя входного файла: problem3.in
Имя выходного файла: problem3.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Задан детерминированный конечный автомат. Требуется определить количество допускаемых им слов по модулю 10^9 + 7
В первой строке содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно ( 1 ≤ n; m ≤ 100000 , 1 ≤ k ≤ n).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Выведите количество слов, допускаемых автоматом по модулю 10^9 + 7. Если таких слов существует бесконечно много, требуется вывести 1
problem3.in
1 1 1
1
1 1 a
problem3.out
-1
problem3.in
3 5 1
3
1 2 a
1 2 b
2 3 a
2 3 b
2 3 c
problem3.out
6
Имя входного файла: problem4.in
Имя выходного файла: problem4.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Задан детерминированный конечный автомат и число l. Требуется определить количество допускаемых им слов длины l по модулю 10^9 + 7
В первой строке содержатся числа n, m, k и l — количество состояний, переходов и допускающих состояний в автомате, а также длина слов ( 1 ≤ n; m ≤ 100 , 1 ≤ k ≤ n, 1 ≤ l ≤ 10^3 ).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Выведите количество слов длины l, допускаемых автоматом, по модулю 10^9 + 7.
problem4.in
3 6 1 1
3
1 2 a
1 2 b
2 3 a
2 3 b
2 3 c
1 3 q
problem4.out
1
Имя входного файла: problem5.in
Имя выходного файла: problem5.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Задан недетерминированный конечный автомат и число l. Требуется определить количество допускаемых им слов длины l по модулю 10^9 + 7.
В первой строке содержатся числа n, m, k и l — количество состояний, переходов и допускающих состояний в автомате, а также длина слов ( 1 ≤ n; m ≤ 100 , 1 ≤ k ≤ n, 1 ≤ l ≤ 10^3 ).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что алгоритм Томпсона найдёт такой детерминированный автомат, распознающий тот же язык, имеющий не более 100 состояний.
Требуется выдать количество слов длины l, допускаемых автоматом, по модулю 10^9 + 7.
problem5.in
3 6 1 1
3
1 2 a
1 2 b
2 3 a
2 3 b
2 3 c
1 3 q
problem5.out
1
Имя входного файла: isomorphism.in
Имя выходного файла: isomorphism.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайта
Задано два детерминированных конечных автомата. Определить, изоморфны ли они друг другу. Гарантируется, что все состояния автоматов достижимы.
Во входном файле находятся два описания ДКА. Формат описания следующий:
В первой строке описания содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно. ( 1 ≤ n; m ≤ 100000, 1 ≤ k ≤ n).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Требуется выдать строку "YES", если автоматы изоморфны, или "NO" в противном случае.
isomorphism.in
3 3 1
3
1 2 a
1 3 c
2 3 b
3 3 1
2
1 3 a
1 2 c
3 2 b
isomorphism.out
YES
Автоматы называются изоморфными, если существует биекция между их вершинами такая, что сохраняются все переходы, терминальные состояния соответствуют терминальным а начальные - начальным.
Имя входного файла: equivalence.in
Имя выходного файла: equivalence.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайта
Задано два детерминированных конечных автомата. Определить, эквивалентны ли они друг другу.
Во входном файле находятся два описания ДКА. Формат описания следующий:
Во первой строке описания содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно. ( 1 ≤ n; m ≤ 1000 , 1 ≤ k ≤ n).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Требуется выдать строку "YES", если автоматы эквивалентны, или "NO" в противном случае.
equivalence.in
1 1 1
1
1 1 a
2 2 2
1 2
1 2 a
2 2 a
equivalence.out
YES
Автоматы называются эквивалентными, если они допускают один и тот же язык
Имя входного файла: minimization.in
Имя выходного файла: minimization.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайта
Задан детерминированный конечный автомат. Требуется построить эквивалентный ему автомат с минимальным количеством состояний.
Во первой строке входного файла содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно. ( 1 ≤ n; m ≤ 1000 , 1 ≤ k ≤ n).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Требуется выдать результирующий автомат в том же формате.
minimization.in
2 2 2
1 2
1 2 a
2 2 a
minimization.out
1 1 1
1
1 1 a
В следующей задаче требуется сделать то же самое, но с более жесткими ограничениями.
Имя входного файла: fastminimization.in
Имя выходного файла: fastminimization.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайта
Задан детерминированный конечный автомат. Требуется построить эквивалентный ему автомат с минимальным количеством состояний.
Во первой строке входного файла содержатся числа n, m и k — количество состояний, переходов и допускающих состояний в автомате соответственно. ( 1 ≤ n; m ≤ 50000 , 1 ≤ k ≤ n).
В следующей строке содержатся k чисел — номера допускающих состояний (состояния пронумерованы от 1 до n).
В следующих m строках описываются переходы в формате "abc", где a — номер исходного состояния перехода, b — номер состояния, в которое осуществляется переход и c — символ (строчная латинская буква), по которому осуществляется переход.
Стартовое состояние автомата всегда имеет номер 1. Гарантируется, что из любого состояния не более одного перехода по каждому символу.
Требуется выдать результирующий автомат в том же формате.
fastminimization.in
2 2 2
1 2
1 2 a
2 2 a
fastminimization.out
1 1 1
1
1 1 a