Mhocskian Languages
Οι γλωσσολόγοι μελετούν αυτή τη στιγμή τα Mhocskian, τη γλώσσα των γηγενών κατοίκων του νησιού Mhocsky. Οι γλωσσολόγοι βρήκαν μια περιγραφή του τρόπου με τον οποίο οι ιθαγενείς κατασκευάζουν λέξεις στα Mhocskian, και μια λίστα με λέξεις. Οι γλωσσολόγοι θα ήθελαν τώρα να μάθουν ποιες από τις λέξεις της λίστας είναι έγκυρες Mhocskian λέξεις.
Κανόνες
Οι λέξεις στα Mhocskian κατασκευάζονται σύμφωνα με ένα σύνολο κανόνων. Αυτοί οι κανόνες περιλαμβάνουν δύο τύπους συνιστωσών: μεταβλητές και τερματικά. Μια μεταβλητή είναι ένα κεφαλαίο γράμμα που χρησιμοποιείται στην περιγραφή των κανόνων. Ένα τερματικό είναι ένα πεζό γράμμα που αποτελεί μέρος μιας λέξης Mhocskian.
Υπάρχουν δύο τύποι κανόνων. Ο πρώτος τύπος κανόνα σάς επιτρέπει να αντικαταστήσετε μια μεταβλητή με δύο μεταβλητές με αυτή τη σειρά και γράφουμε ως σύντομη μορφή για αυτόν τον τύπο κανόνα. Ο δεύτερος τύπος κανόνα σάς επιτρέπει να αντικαταστήσετε μια μεταβλητή με ένα τερματικό και γράφουμε ως μια σύντομη μορφή για αυτόν τον τύπο κανόνα.
Μία από τις μεταβλητές είναι η μεταβλητή έναρξης. Μια λέξη αποτελείται από πεζά γράμματα από το Αγγλικό αλφάβητο. Είναι έγκυρη λέξη Mhocskian εάν, ξεκινώντας από τη μεταβλητή έναρξης, είναι δυνατό ακολουθήστε μια σειρά κανόνων για να αποκτήσετε το .
Παράδειγμα
Έστω ότι έχουμε τις μεταβλητές {}, τα τερματικά {} και τους κανόνες {}.
Η λέξη "ab" είναι μια έγκυρη λέξη Mhocskian επειδή μπορεί να κατασκευαστεί με τον ακόλουθο τρόπο:
. Η λέξη "a" μπορεί να κατασκευαστεί . Η λέξη "b" δεν μπορεί να κατασκευαστεί.
Είσοδος
Στην πρώτη γραμμή, δύο ακέραιοι και με αυτή τη σειρά.
Στη δεύτερη γραμμή, χωρισμένα με κενό κεφαλαία γράμματα, οι μεταβλητές. Η πρώτη μεταβλητή της γραμμής είναι πάντα η μεταβλητή έναρξης.
Στην τρίτη γραμμή, χωρισμένα με κενό μικρά γράμματα, τα τερματικά.
Στην τέταρτη γραμμή, υπάρχει ένας ακέραιος . Ακολουθούν γραμμές, καθεμία είναι της μορφής που αντιπροσωπεύει έναν κανόνα .
Στην επόμενη γραμμή, υπάρχει ένας ακέραιος . Ακολουθούν γραμμές, καθεμία της μορφής , που αντιπροσωπεύει έναν κανόνα .
Στην επόμενη γραμμή, υπάρχει ένας ακέραιος . Ακολουθούν γραμμές, με καθεμία να περιέχει μία λέξη που είναι φτιαγμένη μόνο από μικρά γράμματα.
Έξοδος
Η έξοδος πρέπει να περιέχει γραμμές. Στη γραμμή , εκτυπώστε 1
αν η -οστη λέξη είναι μία λέξη Mhocskian, αλλιώς 0
.
Περιορισμοί
Καθεμία από τις λέξεις στη λίστα των γλωσσολόγων θα έχει μήκος μεταξύ και .
Παράδειγμα
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