#P1468. 时间复杂度

时间复杂度

<style type="text/css"> </style>

ACM里面,计算复杂度是一项非常重要的事情,常见的复杂度格式有三种:

  1. O(n)
    O(lg(n))
    O(sqrt(n))

一个算法往往有多种解法,每种解法的复杂度有上述常见的的复杂度组合成,例如排序的两种算法:

  1. 快速排序: 时间复杂度为O(n*lg(n))

  2. 冒泡排序: 时间复杂度为O(n*n)

现在给定你一个nm个算法复杂度,请确定这些复杂度是否会超时。若复杂度计算结果大于100000000,则为超时(TLE),否则输出计算的复杂度,输出的结果保留两位小数。

(lg(n)表示以2为底数,n为真数的值)

Input

第一行输入n (1≤n≤10000), m(1≤m≤100), 其中n为题目描述的数,m为算法复杂度的个数。
接下来m行,每行为一个串,每个串都包含O()任何括号里面的数据保证仅由n,lg(),sqrt(),*组成并且合法。如sample input所示。

Output

对于每个串,若计算出来的复杂度大于100000000,则输出TLE,否则输出该复杂度的计算次数

Sample Input

10000 6
O(n*n)
O(n*n*n)
O(sqrt(n))
O(lg(n))
O(n*lg(n))
O(n*lg(n*lg(n)))

Sample Output

100000000.00
TLE
100.00
13.29
132877.12
170197.33

HINT

关于lg(n)的C语言代码可以这样写
log(n) / log(2)

Source