1 / 4
Mar 2017

Cześć! Przesłałem rozwiązanie zadania z obliczaniem współczynnika dwumianowego (dwumianu Newtona). Sędzia wyświetla mi błędną odpowiedź mimo, że program swój przetestowałem mnóstwem różnych przykładów danych wejściowych i nie zauważyłem, aby cokolwiek zostało źle obliczone.
Sprawdzałem w szczególności takie pary liczb, jak ( 0 0 ), ( 3849 0 ), ( 3849 3849 ), ( 1 1 ), ( 1 0 ) itp.

Będę bardzo wdzięczny za odnaleziony błąd :slight_smile:

#include<iostream>
using namespace std;

int binom(int n, int k)
{
    if(n - k < k)
        return binom(n, n-k);

    unsigned long long M = 1, L = 1;
    for(int i = n; i > n-k; i--)
        M *= i;
    for(int i = k; i > 1; i--)
        L *= i;
    return (M/L);
}
int main()
{
    int t; cin >> t;
    int * n = new int[t];
    int * k = new int[t];
    for(int i = 0; i < t; i++)
        cin >> n[i] >> k[i];
    for(int i = 0; i < t; i++)
        cout << binom(n[i], k[i]) << endl;

    delete [] n;
    delete [] k;
    return 0;
}

Błędu brak. Użyj jedynie większego typu zmiennej dla licznika i mianownika.

Jeszcze większego, np. long double? Nie pomyślałbym, że unsigned long long (0...2^64-1) może nie wystarczać.