15北京師範大学の新入生の同時試合E題

7383 ワード

E. BQG's Complexity Analysis
いろいろ考えたあげく、ある難題を解決できる2つのアルゴリズムと、ある原因に基づいて(実は神様だから!)、アルゴリズムの時間的複雑さは常に負の整数ではない.
 
しかし、大量の脳力運動を経て、かわいそうな意識がぼんやりしていて、あなたの助けが必要です.今、この2つのアルゴリズムの時間複雑度と、どのアルゴリズムの時間複雑度がもっと優れているかを知りたいと思っています.
Input
最初の行は正の整数で、テストデータのグループ数を表します.
 
各テストデータのセットには1行しかありません.
 
アルゴリズムと時間の複雑さを表す2つの文字列を含み、中間を1つのスペースで区切って、
 
以下はいくつかの約束です.
 
各文字列は厳密に「O(n^k*(logn)^t)」(引用符を含まない)の形式で入力されます.
 
入力に余分なスペースがないことを保証します.
 
以下のような場合にのみ特別な処理が必要となり、
 
(1)このとき「n^k」は「n」に簡略化され、乗数は省略され、
 
(2)このとき「(logn)^k」は「logn」に簡略化され、
 
(3)なお、この場合ゼロ次項及び乗数は省略され、
 
(4)なお、このとき入力列は必ず「O(1)」であり(引用符を含まない)、
 
詳細については、サンプルを参照してください.
Output
テストデータのセットごとに1行出力し、
 
より優れている場合は「First」を出力し、より優れている場合は「Second」を出力し、複雑度が同じ場合は「Both」を出力します(引用符は含まれません).
Sample Input 
7
O(logn) O(1)
O(logn) O((logn)^2)
O(n) O(n^2)
O(n^2) O(nlogn)
O(n(logn)^2) O(n^2*logn)
O(n^2*logn) O(nlogn)
O(n^2*(logn)^2) O(n^2*(logn)^2)

Sample Output 
Second
First
First
Second
First
Second
Both
//             ，           ，      ，    。。。。
         ，         ，           。
  O                  n->+inf ，      n   ，n         log   ，              ，                 。

  
  
  
  

   
   
   
   
     
    
  1. #include<cstdio>  
    2.  
    
  2. #include<cstring>  
    3.  
    
  3. #include<cstdlib>  
    4.  
    
  4. #include<cmath>  
    5.  
    
  5. #include<iostream>  
    6.  
    
  6. #include<algorithm>  
    7.  
    
  7. using namespace std;  
    8.  
    
  8. char s[55];  
    9.  
    
  9. pair<int,int>c[5];  
    10.  
    
  10. int main()  
    11.  
    
  11. {  
    12.  
    
  12.     int T;  
    13.  
    
  13.     scanf("%d",&T);  
    14.  
    
  14.     while(T--)  
    15.  
    
  15.     {  
    16.  
    
  16.         for(int i=0;i<2;i++)  
    17.  
    
  17.         {  
    18.  
    
  18.             scanf("%s",s);  
    19.  
    
  19.             int loc=0;  
    20.  
    
  20.             if(s[2]=='1')  
    21.  
    
  21.             {  
    22.  
    
  22.                 c[i]=make_pair(0,0);  
    23.  
    
  23.                 continue;  
    24.  
    
  24.             }  
    25.  
    
  25.             else if(s[2]=='n')  
    26.  
    
  26.             {  
    27.  
    
  27.                 loc=3;  
    28.  
    
  28.                 if(s[3]=='^')  
    29.  
    
  29.                 {  
    30.  
    
  30.                     int pp=0;  
    31.  
    
  31.                     loc++;  
    32.  
    
  32.                     while(s[loc]>='0' && s[loc]<='9')  
    33.  
    
  33.                         pp=pp*10+s[loc++]-'0';  
    34.  
    
  34.                     c[i].first=pp;  
    35.  
    
  35.                 }  
    36.  
    
  36.                 else c[i].first=1;  
    37.  
    
  37.             }  
    38.  
    
  38.             else c[i].first=0;  
    39.  
    
  39.             if(s[loc]==')')c[i].second=0;  
    40.  
    
  40.             else  
    41.  
    
  41.             {  
    42.  
    
  42.                 int pp=0,len=strlen(s);  
    43.  
    
  43.                 while(loc<len && (s[loc]<'0' || s[loc]>'9'))loc++;  
    44.  
    
  44.                 while(loc<len && s[loc]>='0' && s[loc]<='9')  
    45.  
    
  45.                     pp=pp*10+s[loc++]-'0';  
    46.  
    
  46.                 if(pp==0)c[i].second=1;  
    47.  
    
  47.                 else c[i].second=pp;  
    48.  
    
  48.             }  
    49.  
    
  49.         }  
    50.  
    
  50.         if(c[0]<c[1])printf("First
    "    );  
    51.  
    
  51.         else if(c[0]>c[1])printf("Second
    "    );  
    52.  
    
  52.         else printf("Both
    "    );  
    53.  
    
  53.     }  
    54.  
    
  54.     return 0;  
    55.  
    
  55. }  
    56.
Base 64およびMd 5の使用
任意の2点間の最短経路問題(Floyd-Warshallアルゴリズム)