落絮飞雁

顺流而下,把梦做完

【十二月校赛】1002会超时吗?

会超时吗?

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 208    Accepted Submission(s): 74

Problem Description
随着计算机的飞速发展,现在大多数同学手中的计算机的CPU都是2.0Ghz以上。
我们可以大致的认为计算机的运行频率约为2*109Hz(当然,如果是多核CPU的话运行速度会更快,这个暂时不考虑)。

可能大家对于计算机的运行速度没有准确的概念,我们在HDOJ上对下面代码进行测试,只需要500MS左右就可以算出结果,当然这个速度比我们平常用的电脑会快一点。

尽管现在的计算机运行速度已经很快了,但是还是无法满足人们不断增长的需求,因此,程序的效率是非常重要的。比如,在ACM比赛中,那些运行效率不符合要求的代码常常会得到TLE的结果。

不过在很多情况下,可以通过算法的时间复杂度和题目的时限以及经验来大致的判断你的代码是否会超时。

可能有些同学不明白什么是算法的时间复杂度,这么说吧,时间复杂度可以用O(n),O(n*n),O(n*n*n), O(log(n)),O(sqrt(n))等等来表示。作为初学者,假设我们只用O(n)和O(n*n)的算法。
对于一个ACM题目,假如他给你的样例总数为T,算法复杂度(假设为O(n)), n的大小,以及限制时间t。那么我们可以用T*n来估计大致的运行次数。如n=106, T=100。那么我们可以大致的认为,程序运行的次数在108这个数量级。

现在,我们粗略的认为:
如果运算量为108或者更少的情况下,这个代码是肯定不会超时的。
如果在108到109之间 ( >108 且 ≤109 )可能会超时,可能不会超时。
如果大于109 ,那么它会超时。

举个例子,如果时间t=2 (s),T=200 ,n=103 ,时间复杂度 O(n*n)。那么运算量为 T*n*n/t=108, 这是安全的。

 

 

Input
输入包含多个测试样例,以EOF结束。
每一行包含一个字符串 s(长度≤ 10 ),3个整数 n , T , t 。
s,n,T,t 之间都包含一个空格。
字符串s表示算法复杂度,我们保证肯定是O(n*n)或者O(n)。
n , T ,t (1≤ n, T ≤105 , 1≤t≤10 )均表示题目描述中所提到的变量。
n, t , T 均会以数字形式如100000出现,不会以指数形式105或者10^5的形式出现。
 

 

Output
对于每一个测试样例,输出yes表示不会超时,输出no表示会超时,输出maybe表示不确定。
 

 

Sample Input
O(n) 100000 10000 10
O(n*n) 10000 100 10
 

 

Sample Output
yes
maybe
 
Hint

int型变量可能不易解决这个问题,推荐用double型或者__int64型。

#include
#include
main()
{
    long long int a,b,j,n,m,k,len,i,T,t;
    char p[5];
    while(scanf("%s",&p)!=EOF)
    {
        scanf("%I64d %I64d %I64d%*c",&n,&T,&t);
        len=strlen(p);
        if(len==4)
        {
            m=(T/t)*n;
        }
        else if(len==6)
        {
            m=(T/t)*n*n;
        }
        if(m

 


原文标题:【十二月校赛】1002会超时吗?|落絮飞雁的个人网站
原文链接:https://www.luoxufeiyan.com/2013/12/28/%e3%80%90%e5%8d%81%e4%ba%8c%e6%9c%88%e6%a0%a1%e8%b5%9b%e3%80%911002%e4%bc%9a%e8%b6%85%e6%97%b6%e5%90%97%ef%bc%9f/
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。