UVa : 11711 (Turing)

// http://uva.onlinejudge.org/external/117/11711.html
// Runtime: 0.092s
// Tag: Adhoc, Simulation 

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on April 15, 2011, 10:19 AM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)
enum STATUS {MLE, TLE, WA, AC, Default};

using namespace std;

struct state {
    int q_prev;
    int c_prev;
    int q_next;
    int c_next;
    char mov;
} a [1000 + 5];

int tape [1000 + 5];

void reset (int x)
{
    Set (tape, 0);
    For (i, 0, x) tape [i] = 1;
}

bool judge (int y)
{
    For (i, 0, y) if ( tape [i] == 0 ) return false;
    For (i, y, 1000) if ( tape [i] == 1 ) return false;
    return true;
}

int main(int argc, char** argv)
{
    //Read ("in");
    //Write ("out");
    
    int n, m;

    while ( scanf ("%d %d", &n, &m) ) {
        if ( n == 0 && m == 0 ) break;

        map <pair <int, int>, int> rules;

        For (i, 0, n) {
            scanf ("%d %d %d %d %c", &a [i].q_prev, &a [i].c_prev, &a [i].q_next, &a [i].c_next, &a [i].mov);
            rules [make_pair(a [i].q_prev, a [i].c_prev)] = i + 1;
        }

        For (i, 0, m) {
            int x, y;
            scanf ("%d %d", &x, &y);
            STATUS status = Default;
            reset (x);
            
            int curr_state = 0;
            int curr_index = 0;
            int total_iteration = 0;
            int rules_no = rules [make_pair (curr_state, tape [curr_index])];

            while ( rules_no && total_iteration <= 10000 ) {
                curr_state = a [rules_no - 1].q_next;
                tape [curr_index] = a [rules_no - 1].c_next;

                if ( a [rules_no - 1].mov == 'R' ) curr_index++;
                else curr_index--;

                if ( curr_index < 0 || curr_index == 1000 ) {
                    status = MLE;
                    break;
                }

                rules_no = rules [make_pair (curr_state, tape [curr_index])];
                total_iteration++;
            }

            if ( total_iteration > 10000 ) status = TLE;
            if ( status == Default) status = judge (y) ? AC : WA;

            if (status == TLE ) printf ("TLE\n");
            else if (status == MLE ) printf ("MLE\n");
            else if (status == WA ) printf ("WA\n");
            else printf ("AC\n");
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE