时间复杂度

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

  1. O(n)

  2. O(lg(n))

  3. O(sqrt(n))

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

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

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

现在给定你一个n,m个算法复杂度,请确定这些复杂度是否会超时。若复杂度计算结果大于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