SPOJ dwumiany

Question

Witam, pracując nad zadaniem ze SPOJa o dwumianach:
https://pl.spoj.com/problems/BINOMS/
Szukałem pomocy na forum i trafiłem na zagadnienie "symbol Newtona". Wykorzystałem to w swoim programie, program działa, oblicza przykłady ze SPOJa, jednak sędzia zwraca błędną odpowiedź. Ktoś doradzi gdzie szukać błędu?

#include <iostream>
#include <cmath>
using namespace std;

double symbolNewtona (double n, double k)
{
    double wynik = 1;
    for (int i=1; i<=k; i++)
    {
        wynik = (wynik*(n-i+1))/i;
    }
    return wynik;

}

int main()
{
    int ile;
    cin >> ile;

    for (int i=0; i<ile; i++)
    {   double wynik;
        double k,n;
        cin >>n>>k;
        cout << symbolNewtona(n,k) << endl;

    }
    return 0;
}

 

Comments

Jak się rozwiązuje tego typu zadania na SPOJu to lepiej unikać liczb zmiennoprzecinkowych

---

Zmiana na inta nie pomogła. 

#include <iostream>
#include <cmath>
using namespace std;

int symbolNewtona (int n, int k)
{
    int wynik = 1;
    for (int i=1; i<=k; i++)
    {
        wynik = (wynik*(n-i+1))/i;
    }
    return round(wynik) ;

}

int main()
{
    int ile;
    cin >> ile;

    for (int i=0; i<ile; i++)
    {   int wynik;
        int k,n;
        cin >>n>>k;
        cout << symbolNewtona(n,k) << endl;

    }
    return 0;
}

 

---

W linii 10. dzielisz inta przez inta, co też zwraca inta. Więc ten round w linii 12. nic nie robi.

Answer 1

Zastosuj zaokrąglenie w funkcji wynik. Funkcja powina zwracać liczbę całkowitą.

Comments

#include <iostream>
#include <cmath>
using namespace std;

int symbolNewtona (int n, int k)
{
    int wynik = 1;
    for (int i=1; i<=k; i++)
    {
        wynik = (wynik*(n-i+1))/i;
    }
    return round(wynik) ;

}

int main()
{
    int ile;
    cin >> ile;

    for (int i=0; i<ile; i++)
    {   int wynik;
        int k,n;
        cin >>n>>k;
        cout << symbolNewtona(n,k) << endl;

    }
    return 0;
}

Zmiana typu na int oraz zaokrąglenie nie pomogły.

Answer 2

long long symbolNewtona(long long n, long long k)
{
	if (2 * k > n)
		k = n - k;
	long long wynik = 1;
	for (int i = 1; i <= k; i++)
    {
		wynik = wynik * (n - i + 1) / i;
    }
	return wynik;
}