c++ - CodeChef 每日训练错误答案

Question

因此，在上一次 CodeChef 竞赛(2 月 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 循环中，当我执行 output+= 时，我做了一个小改动。

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

问题是我的选择函数没有(至少)正确处理一种情况。如果 compartments[i] = 0 和 tickets = 1，答案应该是 0，因为从 1 事物中选择 0 事物的方法是 0。但是，0 和 1 的阶乘都是 1，并且阶乘(在我的函数中) -1 (0-1) 也是 1，所以我的选择返回 1/(1*1)。哎呀。不知道为什么我花了这么长时间才找到这个。我从未测试过这种情况。抱歉浪费了时间，我还在学习。