SPOJ：KURUK14這兩個答案有什麼區別

-1

我已經解決了this的問題並獲得了AC。我的問題與以下兩種方法的等價性有關。第一個代碼被接受了，而第二個代碼沒有。據我所知，任何人都可以想到的所有（有效）測試用例都完全相同。我錯了嗎？如果是這樣，什麼樣的測試用例可以區分它們？SPOJ：KURUK14這兩個答案有什麼區別

代碼＃1（接受一個）：

#include <cstdio> 

bool* M; 

bool proc(int N){ 
    for(int j=0;j<=N;j++){ 
     M[j]=false; 
    } 
    for(int i=0;i<N;i++){ 
     int a=0; 
     scanf("%d",&a); 
     if(a>=N) 
      return false; 
     else if(!M[a]) 
      M[a]=true; 
     else if(!M[N-1-a]) 
      M[N-1-a]=true; 
    } 
    bool f = true; 
    for(int k=0;k<N;k++) 
    { 
     f = f && M[k]; 
    } 
    return f; 
} 

int main() { 
    M=new bool[1002]; 
    int num=0; 
    scanf("%d",&num); 
    while(num){ 
     int N=0; 
     scanf("%d",&N); 
     if(proc(N)) 
      printf("YES\n"); 
     else 
      printf("NO\n"); 
     num--; 
    } 
    return 0; 
}

代碼＃2（WA）：

#include <cstdio> 

bool* M; 

bool proc(int N){ 
    for(int j=0;j<=N;j++){ 
     M[j]=false; 
    } 
    for(int i=0;i<N;i++){ 
     int a=0; 
     scanf("%d",&a); 
     if(a>=N) 
      return false; 
     else if(!M[a]) 
      M[a]=true; 
     else if(!M[N-1-a]) 
      M[N-1-a]=true; 
     else 
      return false; 
    } 
    return true; 
} 

int main() { 
    //Exactly same as code#1 
}

來源

2015-04-01 Aman Singh

在第一個示例中，您有一個完整的for循環，而您在第二個示例中沒有這個循環。 – NathanOliver 2015-04-01 12:35:48

@NathanOliver謝謝，但這對我來說已經很明顯了。我的問題是，我不能拿出任何測試用例來區分這兩個。 – 2015-04-01 12:53:33

的錯誤無關，與算法本身—這是非常有可能的兩種算法是正確的。但第二個執行是錯誤的。

當你到達一個應該返回NO的測試用例時，你提前退出了該函數。這意味着當前測試用例中有一些數字在輸入中未被讀取，這當然會徹底混淆進一步的閱讀。這意味着該錯誤僅在T > 1時纔會顯示。

來源

2015-04-01 13:42:25 Angew

以下是[Ideone.com]（http://ideone.com/kr21W9）上的演示。 – Angew 2015-04-01 13:43:44

你是對的！這樣一個簡單的錯誤！非常感謝。 – 2015-04-02 07:04:22

SPOJ：KURUK14這兩個答案有什麼區別

回答

相關問題