ICPC Tutorial

ACM-ICPC returns to Singapore in 2015 after a long absence.
There may be new contestants from this region who are joining
ACM-ICPC for the very first time^{1}. This problem
serves as a tutorial for such contestants.

First, let establish the fact that the problems posed in
ICPC are not research problems where nobody on earth knows how
to solve them efficiently. Some people (at least the problem
authors) have solved these problems before. There can be more
than one possible solution to these problems. As the contest
has limited time (5 hours) and each problem has an associated
time penalty, it is always beneficial to pick the easiest
problem to solve first^{2}.

Some problems may look complicated but happen to have a small input size constraint $n$ that allows even a naïve brute force solution to pass. Some other problems may look simple but standard textbook algorithm cannot be used to pass the time limit as the input size constraint $n$ is too big and one has to figure out the special properties that simplify the problem.

In the “Competitive Programming” book^{3} that has
been written specifically for preparing for programming
contests such as ICPC, we have the following compilation of
typical algorithm complexities found in programming
contests:

$t$ |
algorithm complexity for input size $n$ |

1 |
$O(n!)$ |

2 |
$O(2^ n)$ |

3 |
$O(n^4)$ |

4 |
$O(n^3)$ |

5 |
$O(n^2)$ |

6 |
$O(n \log _2 n)$ |

7 |
$O(n)$ |

For this problem, we ignore the constant factor and the
lower terms hidden in the Big O notation, i.e. an $O(g(n))$ algorithm is assumed to
perform **exactly** $g(n)$ operations.

Let $m$ be the number
of operations that the computer used in the contest^{4} can run in one second. Suppose
$m = 100\, 000\, 000$ and
the team is trying to solve a problem with a time limit of one
second. If the team can devise an algorithm of type
$t = 3$, i.e., a rather
slow $O(n^4)$ algorithm,
but the largest $n$
mentioned in the problem description is just $50$, then this algorithm is actually
fast enough and will get “Accepted” since $50^4 = 6\, 250\, 000$ is **less than (or equal to**) $m$.

However, if for another problem also with one second time
limit, the team can only devise an algorithm of type
$t = 5$, i.e. an
$O(n^2)$ algorithm, but
the largest $n$ mentioned
in the problem description is $10\, 001$, then this algorithm is
likely not fast enough to pass the time limit and will get
“Time Limit Exceeded”, since $10\, 001^2 = 100\, 020\, 001$ which
is **greater than** $m$.

Formally, given three integer parameters $m$ $(1
\le m \le 10^9)$, $n$ $(1
\le n \le 10^9)$, and $t
\in [1..7]$, decide if an algorithm of type $t$ with time complexity as described
in the table above can pass the time limit of one second, that
is, performs **less than (or equal to)**
$m$ operations. Output
“AC” (that stands for “Accepted”) if that is the case, or “TLE”
(that stands for “Time Limit Exceeded”) otherwise.

The input consists of three integers in one line: $m$, $n$, and $t$ as elaborated above.

Output a single string “AC” or “TLE” in one line as elaborated above.

Sample Input 1 | Sample Output 1 |
---|---|

100000000 500 3 |
TLE |

Sample Input 2 | Sample Output 2 |
---|---|

100000000 50 3 |
AC |

Sample Input 3 | Sample Output 3 |
---|---|

100000000 10001 5 |
TLE |

Sample Input 4 | Sample Output 4 |
---|---|

100000000 10000 5 |
AC |

Sample Input 5 | Sample Output 5 |
---|---|

19931568 1000000 6 |
TLE |

Sample Input 6 | Sample Output 6 |
---|---|

19931569 1000000 6 |
AC |

**Footnotes**

- Note that if this is the very first time that your University sends a team to compete in an ACM-ICPC regional contest, you should ask your coach to inform the Regional Contest Director to be eligible for the “Best Newcomer Team” award.
- ICPC SG Regional Contest 15 has “First Team to Solve Problem [A/B/C,...]” awards. Note that the presence of such awards may lead some teams to strategically solve a “medium difficulty” problem first at the early stage of the contest, hoping that they end up solving that problem first thus getting the award.
- Teams who advance from this ICPC SG Preliminary Contest 15 will receive a sponsored copy of the Competitive Programming 3 book at the onsite registration of ICPC SG Regional Contest 15.
- Usually, experienced teams will perform tests during practice contest to measure $m$.