시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 88 | 20 | 10 | 20.408% |
Bob is one of the best students of the Formal Languages class. Now he is learning about context free grammars in the Chomsky Normal Form (CNF). Such a grammar consists of:
If A ∈ N, we define L(A), the language generated by A, as follows:
L(A) = { wz | w ∈ L(B), z ∈ L(C), where A → BC ∈ R } ∪ { a | A → a ∈ R }.
The language generated by the grammar with start symbol S is defined to be L(S). Bob must solve the following problem: for a given context free grammar in CNF, on input string x, determine whether x is in the language generated by the grammar, L(S).
The program input is from a text file. It starts with the input string x (|x|<=1000). Follows the grammar rules, in the form ABC or Aa, each on a separate line. We consider that the start symbol is always S.
The input data are correct and terminate with an end of file. The program prints the result to the standard output from the beginning of a line.
The program prints 1 if the string is in the language generated by the grammar, 0 otherwise.
a SAB Sa Ab
1
ab SAB Sa Ab
0
ab SAB Sa Ab Ba
0
Input/output samples are given in the table below. There are three tests. The first two use the same grammar: SAB, Sa, Ab (S→AB, S→a, A→b). For the first test the input string is a, and the result is 1, while for the second test the input string is ab and the result is 0.
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2014 G번