程序设计在线评测(Online Judge)


问题 1049. -- 时间复杂度

1049: 时间复杂度

时间限制: 1 Sec  内存限制: 128 MB
提交: 32  解决: 10
[提交][状态][讨论版]

题目描述

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

1、 O(n)

2、 O(lg(n))

3、 O(sqrt(n))

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

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

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

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

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

输入

第一行输入n (1n10000), m(1m100), 其中n为题目描述的数,m为算法复杂度的个数。

接下来m行,每行为一个串,每个串都包含O()任何括号里面的数据保证仅由n,lg(),sqrt(),*组成并且合法。如sample input所示。

输出

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

样例输入

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)))

样例输出

100000000.00
TLE
100.00
13.29
132877.12
170197.33

提示

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


log(n) / log(2)

来源

[提交][状态][讨论版]