CodeChef Daily Train Wrong Answer

Итак, в последнем конкурсе на CodeChef (февральский повар) у меня было то, что я считал рабочим алгоритмом для этой проблемы в течение примерно 15 минут, но не смог получить правильный ответ. Я пробовал навсегда, я проверил несколько вещей, я не понимаю, где моя ошибка. Мой общий алгоритм соответствует редакции проблемы, но у меня есть ошибка где-то я не могу найти, я думаю.CodeChef Daily Train Wrong Answer

Ссылка на проблему - 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

Таким образом, правильный код приведен ниже.

Внутри цикла while, когда я делаю вывод + =, я делаю небольшое изменение.

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

Проблема в том, что моя функция выбора не обрабатывает (по крайней мере) один случай правильно. Если отсеки [i] = 0 и билеты = 1, ответ должен быть 0, так как способы выбора 0 вещей из 1 вещи равны 0. Однако факториал 0 и 1 равны 1, а факториал (по моей функции) -1 (0-1) также равно 1, поэтому мой выбор возвращает 1/(1 * 1). К сожалению. Не знаю, почему мне так долго приходилось это искать. Я никогда не тестировал этот случай. Извините за потраченное время, я все еще учусь.

источник

2012-02-23 17:04:42 kchinger

CodeChef Daily Train Wrong Answer

ответ

Смежные вопросы