CodeChef Daily Train錯誤的答案

因此，在CodeChef（February Cook-Off）的最後一次比賽中，我在大約15分鐘內就認爲這是一個針對此問題的工作算法，但無法得到正確的答案。我試過了，我查了很多東西，我不明白我的錯誤在哪裏。我的一般算法與該問題的編輯相匹配，但我有一個錯誤，我無法找到我猜的地方。CodeChef Daily Train錯誤的答案

鏈接的問題 - http://www.codechef.com/problems/daily

這是一個在C++。代碼如下。基本上我只是讀門票數量，汽車數量，迭代汽車。讀取字符串，減少隔間數組，對隔間進行組合（選擇），添加到輸出，完成。

在所有的測試案例和一些我想出來的工作很好。這裏有一些不需要的東西，只是我的CodeChef模板的一部分。

任何幫助表示讚賞。

#include <iostream> 
#include <time.h> 
#include <string> 
#include <math.h> 
using namespace std; 

const double PI=2*acos(0.0); 
#define sqr(x) ((x)*(x)) 
#define min(a,b) ((a)<(b)?(a):(b)) 
#define max(a,b) ((a)>(b)?(a):(b)) 



int factorial(int input){ 
    int output = 1; 
    while(input>1){ 
     output*=input--; 
    } 
    return output; 
} 

int choose(int n, int k){ 
    int output = 0; 
    output = factorial(n)/(factorial(k)*factorial(n-k)); 
    return output; 
} 

int main(){ 

#ifndef ONLINE_JUDGE 
    clock_t tStart = clock(); 
    freopen("in.txt","r",stdin); 
    //freopen("out.txt","w",stdout); 
    //freopen("time.txt","w",stderr); 
#endif 

    int tickets; 
    cin >> tickets; 
    int cars; 
    cin >> cars; 
    string input; 
    int output = 0; 
    int compartments[9]; 
    while(cars-->0){ 
     for(int i = 0;i<9;i++){ 
      compartments[i] = 6; 
     } 
     cin >> input; 
     for(int i = 0;i<=35;i++){ 
      compartments[i/4] -= (input.at(i)-48); 
     } 
     for(int i = 36;i<=53;i++){ 
      compartments[8-((i-36)/2)] -=(input.at(i)-48); 
     } 
     for(int i = 0;i<9;i++){ 
      output+=choose(compartments[i],tickets); 
     } 

    } 

    cout << output; 

#ifndef ONLINE_JUDGE 
    fprintf(stderr,"Completed in %.0f msec\n",(double)(clock()-tStart)); 
#endif 

    return 0; 
}

來源

2012-02-22 kchinger

好吧，所以我找到了答案，但我不知道爲什麼。我決定這個問題必須在我的選擇函數中，所以當我知道它不會返回0時（即n> = k），我只嘗試調用它。這工作。但我不明白爲什麼。如果n kchinger 2012-02-23 01:42:59

所以正確的代碼如下。

在while循環中，當我輸出+ =時，我做了一個小改動。

if(compartments[i]>=tickets){ 
    output+=choose(compartments[i],tickets); 
}

問題是我的選擇功能不能正確處理（至少）一種情況。如果車廂[i] = 0且車票= 1，則答案應該爲0，因爲從1中選擇0個東西的方法是0.但是，0和1的階乘都是1，因式（在我的函數中）是-1（0-1）也是1，所以我的選擇返回1 /（1 * 1）。哎呀。不知道爲什麼花了我很長時間才發現這一點。我從未測試過這種情況。對不起浪費時間，我還在學習。

來源

2012-02-23 17:04:42 kchinger

CodeChef Daily Train錯誤的答案

回答

相關問題