CodeChef Daily Train Wrong Answer

Question

CodeChef（February Cook-Off）の最後のコンテストで、私はこの問題のアルゴリズムを約15分で解決できると思っていましたが、正解を得ることができませんでした。私は永遠に試しました、私は複数のものをチェックしました、私は間違いがどこにあるのか分かりません。私の一般的なアルゴリズムは問題の編集にマッチしますが、どこかで私が推測できないバグがあります。問題へ

リンク - 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; 
} 

Answer 1

正しいコードは以下のとおりです。

whileループの中で、出力+ =を行うと、私は小さな変更を行います。

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

問題は、私のchoose関数が（少なくとも）1つのケースを正しく処理しないことです。コンパートメント[i] = 0とチケット= 1の場合、1つの事から0つのものを選択する方法は0なので、答えは0になります。しかし、0と1の階乗は両方とも1であり、（私の関数では）階乗-1（0-1）も1なので、私の選択は1 /（1 * 1）を返します。おっとっと。なぜこれが見つからないのか分かりません。私はその事を決してテストしなかった。無駄な時間に申し訳ありません、私はまだ学んでいます。