dwumiany - spoj

0

Próbuję rozwiązać następujące zadanie: http://pl.spoj.com/problems/BINOMS/ Według sędziego mój kod zwraca błędną odpowiedź. Proszę o wskazówki gdzie może być błąd. Dla danych testowych podanych w treści zadania program zwraca dobre odpowiedzi, wpisałem też kilka innych testów np 1000, 999 i wynik też był prawidłowy.


#include <iostream>

using namespace std;

int main()
{
    unsigned short int t, n, k;
    long double result;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        if((n == 0) || (k == 0))
        {
            cout<<"1"<<endl;
        }
        else
        {
            result = 1;
            for(int i = 1; i <= k; ++i)
            {
                result = result * (n - i + 1) / i;
            }

            cout<<result<<endl;
        }
    }

    return 0;
}
0

result = result * (n - i + 1) / i; - matematycznie się zgadza, zaś programistycznie nie.
Ponieważ może się okazać że w kolejnej iteracji nie będzie się dzielić przez i bez reszty.
Poza tym zastanów się nad takim dodatkiem: if(k+k>n) k=n-k+1;
oraz rozważ:

                if(!k) result=1;
                else if(!n) result=0;
                else
                  {
                   result=1;
                   ...
                  }
                cout<<result<<endl;
0

wykonuj jedno mnożenie i dzielenie naraz i licz na doublach, na końcu zaokrąglij wynik.

0

przeczytaliście zadanie, zanim daliście te rady?
Problem tutaj jest typ danych, po cholerę wcisnąłeś te "short" dla n i k? W zadaniu stoi jak byk maksymalny wynik to 1e9.
takiej pary danych nie jesteś wstanie wczytać do short int: 1000000000 1


edit:
Takie wejście powinno dać ci dwa razy maksymalną wartość 1000000000:

2
1000000000 1
1000000000 999999999

Jak naprawisz short zaliczysz tylko pierwszą odpowiedź, na drugiej twój kod nadal zawiedzie (brakuje 2 linijek).

0

0 <= k <= n <= 1000 - problemem nie był short , tylko sposób liczenia. Zadanie już zaliczone - zmodyfikowałem tylko sposób liczenia, a wynik zapisywałem do unsigned long long int. W każdym razie dzięki za odpowiedzi w temacie :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0