Transition table na DFA, pozor na cyklení.
Test00 obsahoval čtyři uzly, z nichž všechny byly finální, neobsahovaly cyklus, většina na sebe ukazovala plnou abecedou, některé neukazovaly hranou a. Řešení testu00 mělo vyjít 333.
Je zde někdo, komu kód nepadal na time limit? Marně jsem zjišťoval, v čem jsem byl tak pomalý.
Nejprve proženu data rychlým tarjanem (jehož mám funkčního z dřívějška). Zabiju uzly, které se cyklí. (Ignoruju případ cyklu nefinálních uzlů, z nichž vede svinská hrana na uzel finální.) A pak projdu stavy dle mě velmi úsporně pomocí bufferování… http://pastebin.com/6mGDtpDQ
Celý zdroják mám k dispozici zde: http://upload.edvard.cz/oi/pal_140205.zip
Můj kód řeší public 1,(2),3 a test 01. Testy 02-09 jsou time expired.
Test 01 dokonce před půl třetí odpoledne psal: your solution is the best from 2 accepted solutions so far… Takže jsme dva prošli testem č. 1. Velmi povzbudivé.
The NFA Counter Let us recall some necessary definitions. The concepts defined here are probably very well known to you, we provide the definitions just for the sake of completeness. A nond eterministic finite automaton (NFA) FA) X is a five-tuple (Σ, Q, q 0 , δ, F) where Σ is an alphabet consisting of A ordered characters a 0 < a 1 < … a A−1 , (1 ≤ A < ∞), Q is a nonempty set of states, Q 0 is a start state, q 0 ∈ Q, δ is a transition function δ: Q× Σ → P(Q), F is a nonempty subset of Q, it is a set of final states. Symbol P(Q) (power set) denotes the set of all subsets of Q including Q itself and empty set. The Task Your task is either to count all different words that are accepted by a given input nondeterministic automaton X or detect that the given input NFA X accepts infinitely many words. Input Input specifies NFA X = (Σ, Q, q 0 , δ, F). The first line contains two integer numbers S and A, where S represents number of states of X and A represents size of alphabet of X. We assume that Q={0,1,2, …, S−1} for S>0, q 0 =0, and Σ is a subset of {‘a’, ’b’, …,’z’} where Σ={a 0 , a 1 , …, a A−1 } for 1≤A≤26. Next S lines contain definition of the transition function δ. Each line starts with state number q j and then contains simple set format listings of sets δ(q j , a 0 ), δ(q j , a 0 ), …, δ(q j , a A−1 ), where simple set format listing of set M is a sequence of k+1 integers (k=|M|) where k is the first element of the sequence followed by all elements of M in arbitrary order. The last line of the input contains simple set format listing of the set F. All values on any input line are separated by one or more spaces. You may assume that S×A ≤ 10000. Output Output contains only one line with the number of all different words accepted by the input NFA X. If the input NFA X accepts infinitely many words then the output is -1. You may assume that the output integer does not exceed 2^60
Example 1 Input: 8 2 0 1 1 0 1 0 2 2 4 2 1 3 0 3 0 1 2 4 2 5 7 0 5 1 6 1 6 6 0 0 7 0 0 3 4 6 7 Output: 4 The transition diagram of the input automaton is depicted on the right-hand side of the input data.
Example 2 Input: 8 2 0 1 1 0 1 0 2 2 4 2 1 3 0 3 0 1 2 4 2 5 7 0 5 1 6 1 6 6 0 0 7 0 0 4 3 4 6 7 Output: -1 The transition diagram of the input automaton is depicted on the right-hand side of the input data. Please note, that Example 1 and Example 2 differ only in their final states specifications. Example 3 Input: 5 3 0 3 1 2 3 3 1 2 4 3 1 3 4 1 2 2 3 2 2 4 2 3 4 2 1 3 1 4 2 3 4 3 0 1 4 1 4 4 0 0 0 3 2 3 4 Output: 60 The transition diagram of the input automaton is depicted on the right-hand side of the input data.