CCO-12 (2012) - 3 (Mhocskian Languages)

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Mhocskian Languages

Οι γλωσσολόγοι μελετούν αυτή τη στιγμή τα Mhocskian, τη γλώσσα των γηγενών κατοίκων του νησιού Mhocsky. Οι γλωσσολόγοι βρήκαν μια περιγραφή του τρόπου με τον οποίο οι ιθαγενείς κατασκευάζουν λέξεις στα Mhocskian, και μια λίστα με λέξεις. Οι γλωσσολόγοι θα ήθελαν τώρα να μάθουν ποιες από τις λέξεις της λίστας είναι έγκυρες Mhocskian λέξεις.

Κανόνες

Οι λέξεις στα Mhocskian κατασκευάζονται σύμφωνα με ένα σύνολο κανόνων. Αυτοί οι κανόνες περιλαμβάνουν δύο τύπους συνιστωσών: μεταβλητές και τερματικά. Μια μεταβλητή είναι ένα κεφαλαίο γράμμα που χρησιμοποιείται στην περιγραφή των κανόνων. Ένα τερματικό είναι ένα πεζό γράμμα που αποτελεί μέρος μιας λέξης Mhocskian.

Υπάρχουν δύο τύποι κανόνων. Ο πρώτος τύπος κανόνα σάς επιτρέπει να αντικαταστήσετε μια μεταβλητή V με δύο μεταβλητές V_1V_2 με αυτή τη σειρά και γράφουμε V \rightarrow V_1V_2 ως σύντομη μορφή για αυτόν τον τύπο κανόνα. Ο δεύτερος τύπος κανόνα σάς επιτρέπει να αντικαταστήσετε μια μεταβλητή V με ένα τερματικό t και γράφουμε V \rightarrow t ως μια σύντομη μορφή για αυτόν τον τύπο κανόνα.

Μία από τις μεταβλητές είναι η μεταβλητή έναρξης. Μια λέξη w αποτελείται από πεζά γράμματα από το Αγγλικό αλφάβητο. Είναι έγκυρη λέξη Mhocskian εάν, ξεκινώντας από τη μεταβλητή έναρξης, είναι δυνατό ακολουθήστε μια σειρά κανόνων για να αποκτήσετε το w.

Παράδειγμα

Έστω ότι έχουμε τις μεταβλητές {S, A, B}, τα τερματικά {a, b} και τους κανόνες {S \rightarrow AB, S \rightarrow a, A \rightarrow a, B \rightarrow b}.

Η λέξη "ab" είναι μια έγκυρη λέξη Mhocskian επειδή μπορεί να κατασκευαστεί με τον ακόλουθο τρόπο:
S \rightarrow AB \rightarrow aB \rightarrow ab. Η λέξη "a" μπορεί να κατασκευαστεί S \rightarrow a. Η λέξη "b" δεν μπορεί να κατασκευαστεί.

Είσοδος

Στην πρώτη γραμμή, δύο ακέραιοι V και T με αυτή τη σειρά.

Στη δεύτερη γραμμή, V χωρισμένα με κενό κεφαλαία γράμματα, οι μεταβλητές. Η πρώτη μεταβλητή της γραμμής είναι πάντα η μεταβλητή έναρξης.

Στην τρίτη γραμμή, T χωρισμένα με κενό μικρά γράμματα, τα τερματικά.

Στην τέταρτη γραμμή, υπάρχει ένας ακέραιος R_1. Ακολουθούν R_1 γραμμές, καθεμία είναι της μορφής V t που αντιπροσωπεύει έναν κανόνα V \rightarrow t.

Στην επόμενη γραμμή, υπάρχει ένας ακέραιος R_2. Ακολουθούν R_2 γραμμές, καθεμία της μορφής V V_1 V_2, που αντιπροσωπεύει έναν κανόνα V \rightarrow V_1V_2.

Στην επόμενη γραμμή, υπάρχει ένας ακέραιος W. Ακολουθούν W γραμμές, με καθεμία να περιέχει μία λέξη που είναι φτιαγμένη μόνο από μικρά γράμματα.

Έξοδος

Η έξοδος πρέπει να περιέχει W γραμμές. Στη γραμμή i, εκτυπώστε 1 αν η i-οστη λέξη είναι μία λέξη Mhocskian, αλλιώς 0.

Περιορισμοί

1 \le V, T \le 26 1 \le R_1 + R_2 \le 30 1 \le W \le 20

Καθεμία από τις λέξεις στη λίστα των γλωσσολόγων θα έχει μήκος μεταξύ 1 και 30.

Παράδειγμα

input

5 2
I S A B C
a b
2
A a
B b
7
I A B
I A C
C S B
S A B
S A C
I S S
S S S
4
abababaaabbbaabbaabb
abab
bbaa
aaabababbaaabbbb

output

1
1
0
1

Comments

There are no comments at the moment.