1227 . Mystery of the Abbey
Description
Have you ever played a board game called "Mystery of the Abbey"?
A monk has been murdered in a medieval French Abbey.
You, as a detective, walk through the Abbey examining clues and questioning each other to find out who is the murderer.
You find some clues and have several hypotheses about the murder.
You need to link them together and prove that your hypotheses are true.
Now, in the 21st century, things become more complicated.
Many things that cannot happen in the Middle Ages happen frequently today,
and the detectives have more hypotheses to prove.
One day, professor Mathomato comes with a good idea:
Usually a hypothesis can be proved using a clue or a combination of clues.
Note that once a hypothesis is proved it becomes a clue to prove other hypotheses.
Therefore, if we formulate the rules of proving those hypotheses,
then we can use computer to speed up this process.
Now, the only difficulty is the program.
Although professor Mathomato is very good at programming,
he does not have time to write the program.
Thus, he would like you to do this for him.
Let's index the hypotheses from 1 to N.
The hypothesis h_i is associated with a rule r_i.
This rule describes the conditions that this hypothesis is true.
A rule is either a sub-rule, or a constant string "C", which means this hypothesis is already proved.
A sub-rule is either a hypothesis id, or a set of sub-rules combined by AND/OR operators.
More formally,
<rule> := C | <sub-rule>
<sub-rule> := <hypothesis>
| (<sub-rule>)
| (<sub-rule>A<sub-rule>A...A<sub-rule>)
| (<sub-rule>O<sub-rule>O...O<sub-rule>)
<hypothesis> := [number between 1 and N]
where A stands for AND operator, O for OR operator.
AND operator means that the outcome is true if and only if all the sub-rules are true.
OR operator means that the outcome is true if and only if at least one of the sub-rules is true.
Note that rules such as (..A..O..) or (..O..A..) are invalid.
A hypothesis in a rule is represented by its index, a decimal integer.
Given the proved hypotheses and all the rules of other hypotheses,
please write a program to find out how many hypothesis are proved in the end.
Input Format
The first line contains an integer, T, specified the number of test cases.
Each test case begins with a line containing an integer N, which means the number of hypotheses you need to deal with.
Then N lines follow, each with either a rule or a single character 'C'.
If the i-th line is 'C', the i-th hypothesis is already proved and becomes a clue.
Otherwise, the rule in the i-th line is the condition that the i-th hypothesis is true.
You can assume that all the rules in input are valid.
There is a blank line between two consecutive test cases.
Output Format
Your program have to output one line per test case.
This line contains the number of hypotheses that can be proved in this test case, including all the initial clues.
1 <= N <= 10000
The length of each rule is no more than 201.
Each index used in the rules is between 1 and N (inclusive).
Sample Input 1
2 3 (2A3) (1A3) C 5 C 1 C (4A1A3) ((1O2)A(1O(3A4)))
Sample Output 1
1 4
Hints
Problem Source
Migrated from old NTUJ.
Ferng
Subtasks
| No. | Testdata Range | Score |
|---|