As you should be aware by now, one of the verdicts you can get when submitting a solution to a problem is Time Limit Exceeded (TLE). This means that the running time of your solution exceeds the time limit set by judges.
Let us assume that the judging server can make 100,000,000 operations per second. Given the time complexity of your solution expressed using big-O notation, maximum size of the input per test case N, the number of test cases T and the time limit for all cases L can your solution run in time?
Assume that your solution uses only simple operations and disregard any other overhead (e.g. I/O).
Input starts with a line containing an integer C (1 <= C <= 100), the number of test cases. C lines follow, each of the format
<time_complexity> N T Lwhere N, T and L are integers as described in the problem statement (1 <= N <= 1,000,000, 1 <= T,L <= 10). and <time_complexity> is one of the following:
O(N), O(N^2), O(N^3), O(2^N), O(N!)Note: We use a very simplified complexity model here and familiarity with big-O notation is not required (or may even be detrimental). Just assume that applying N to the function in the parenthesis is what gives you the total number of operations your solution will use.
For each test case print on one line either "TLE!" if the running time of the solution exceeds the time limit for that test case or "May Pass." if it does not.
13 O(N) 1000 10 10 O(2^N) 1000 10 10 O(N!) 2 10 10 O(N^3) 1000 1 10 O(N^3) 1001 1 10 O(N^2) 10000 1 1 O(N^3) 1000 1 10 O(N^3) 1000000 10 10 O(N!) 1000000 10 10 O(N!) 12 1 10 O(N!) 13 1 10 O(2^N) 27 10 3 O(2^N) 27 1 3
May Pass. TLE! May Pass. May Pass. TLE! May Pass. May Pass. TLE! TLE! May Pass. TLE! TLE! May Pass.