superman

  1 /* Accepted 1011 C++ 00:00.00 988K */
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 int n, m, k;
  7 struct TransitionTable
  8 {
  9     int lSingal, rSingal;
 10     TransitionTable * next;
 11     
 12     void insert(int l, int r)
 13     {
 14         while(next)
 15         {
 16             next -> insert(l, r);
 17             return;
 18         }
 19         TransitionTable * p = new TransitionTable;
 20         p -> lSingal = l;
 21         p -> rSingal = r;
 22         p -> next = NULL;
 23         next = p;
 24     }
 25     
 26     void clear()
 27     {
 28         TransitionTable *p = next;
 29         TransitionTable *q;
 30         while(p)
 31         {
 32             q = p;
 33             p = p -> next;
 34             delete q;
 35         }
 36         next = NULL;
 37     }
 38 }tranT[15][10];
 39 
 40 void readTable()
 41 {
 42     int l, r;
 43     for(int i = 0; i < n; i++)
 44         for(int j = 0; j < k; j++)
 45             while(1)
 46             {
 47                 cin >> l >> r;
 48                 tranT[i][j].insert(l, r);
 49                 if(cin.get() == '\n')
 50                     break;
 51             }
 52 }
 53 
 54 int L;
 55 struct BinTree
 56 {
 57     char transmittingElement;
 58     int left, right;
 59 }Tree[2048 + 1];
 60 
 61 void readTree()
 62 {
 63     char transmittingElement;
 64     for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
 65     {
 66         cin >> transmittingElement;
 67         if(transmittingElement == '*')
 68         {
 69             Tree[i].transmittingElement = -1;
 70             Tree[i / 2].left = Tree[i / 2].right = 0;
 71         }
 72         else
 73         {
 74             Tree[i].transmittingElement = transmittingElement - 'a';
 75             if(i % 2 == 0)
 76                 Tree[i / 2].left = i;
 77             else
 78                 Tree[i / 2].right = i;
 79         }
 80     }
 81 }
 82 
 83 int isValid[2048 + 1][15];
 84 
 85 int PreOrder(int cur, int singal)
 86 {
 87     if(isValid[cur][singal])
 88         return isValid[cur][singal];
 89     TransitionTable * p = tranT[singal][Tree[cur].transmittingElement].next;
 90     if(Tree[cur].left == 0 && Tree[cur].right == 0)
 91     {
 92         while(p)
 93         {
 94             if(p -> lSingal >= n - m && p -> rSingal >= n - m)
 95                 return isValid[cur][singal] = 1;
 96             p = p -> next;
 97         }
 98         return isValid[cur][singal] = -1;
 99     }
100     
101     while(p)
102     {
103         if(PreOrder(cur * 2, p -> lSingal) == 1 && PreOrder(cur * 2 + 1, p -> rSingal) == 1)
104             return isValid[cur][singal] = 1;
105         p = p -> next;
106     }
107     return isValid[cur][singal] = -1;
108 }
109 
110 int main()
111 {
112     int NTA = 0;
113     cin >> n >> m >> k;
114     while(true)
115     {
116         cout << "NTA" << ++NTA << ':' << endl;
117         
118         readTable();
119         while(cin >> L)
120         {
121             if(L == -1)
122                 break;
123             readTree();
124             
125             if(PreOrder(1, 0) == 1)
126                 cout << "Valid" << endl;
127             else
128                 cout << "Invalid" << endl;
129             
130             for(int i = 1; i <= (1 << (L + 1)) - 1; i++)
131                 Tree[i].transmittingElement = Tree[i].left = Tree[i].right = 0;
132             memset(isValid, 0, sizeof(isValid));
133         }
134         
135         for(int i = 0; i < n; i++)
136             for(int j = 0; j < k; j++)
137                 tranT[i][j].clear();
138         
139         cin >> n >> m >> k;
140         if(n == 0 && m == 0 && k == 0)
141             break;
142         else
143             cout << endl;
144     }
145     
146     return 0;
147 }
148