833. Dwumiany [BINOMS]

[etheral6661]

@prynio
Racja, mój błąd. Zatem:
In

1
25 25

Poprawny out

1

[prynio]

Dla 25 25 działał dobrze, ale Twój poprzedni przykład pokazał słabość kodu. Nie wiem czemu, ale dla n=0 wykonywał pętle for (int j=n; j>(n-k); j--) x*=j; chociaż tak na logikę powinien zerwać ją przed pierwszym wykonaniem. W każdym razie dodałem "ręcznie" wyjątek w postaci if (n==0)cout<<x<<endl; i już mi zaliczyło.

Także bardzo dziękuję za pomoc!

[narbej]

W każdym razie dodałem "ręcznie" wyjątek w postaci if (n==0)cout<<x<<endl; i już mi zaliczyło.

No, nono, w takim razie wielki szacunek I za dodanie wyjątku i za zrobienie tego ręcznie, jestem pełen podziwu i uznania

A na ideone.com, można i należy wkleić nie tylko kod programu, ale i testy, abyś i Ty mógł sobie potestować i aby inni też widzieli, że testowałeś: https://ideone.com/9DN2Ui <-- tu niestety twoja stara wersja kodu, bez wstawionego ręcznie wyjątku.

PS
Tak na marginesie, dwumian (1000 3) == dwumian (1000 997), o czym przeczytałbyś i w opisie dwumian'a i w tym wątku, gdybyś czytał.

[prynio]

A na ideone.com, można i należy wkleić nie tylko kod programu, ale i testy, abyś i Ty mógł sobie potestować i aby inni też widzieli, że testowałeś: https://ideone.com/9DN2Ui <-- tu niestety twoja stara wersja kodu, bez wstawionego ręcznie wyjątku.

Dzięki, nie zauważyłem że można tam dodawać testy. Na pewno skorzystam

Tak na marginesie, dwumian (1000 3) == dwumian (1000 997), o czym przeczytałbyś i w opisie dwumian'a i w tym wątku, gdybyś czytał.

To akurat wiem, ale nie bardzo rozumiem jak się ma do tematu. Mogłem zamienić (0 x) na (x x), jeśli to masz na myśli, ale w sumie wyszłoby na to samo co dodanie automatycznego wyniku "1" dla każdego n=0.

[narbej]

To akurat wiem, ale nie bardzo rozumiem jak się ma do tematu

A no taki, że np dla 1000 2 podajesz prawidłowy wynik, ale dla 1000 998 już nie, a oba testy spełniają warunki zadania.
Także np taki test:
40 10 ==> http://www.wolframalpha.com/input/?i=binomial(40,10)

[etheral6661]

Dla 25 25 działał dobrze [...]

Wersja, którą wkleiłeś na ideone wypisywała 0, czyli raczej źle.

Swoją drogą przykład "0 1" był niepoprawny, natomiast "25 15" już tak. Wybaczcie małe zamieszanie.

[wichuraa]

#include<iostream>

using namespace std;


unsigned long long Newton(int n, int k)      
{
	double Wynik = 1;      

	for (unsigned int i = 1; i <= k; i++)  
	{
		Wynik = Wynik * (n - i + 1) / i;    
	}

	return (unsigned long long) Wynik;    
}

int main()


{
	int ile;

	cin >> ile;

	int *tab1 = new int[ile];
	int *tab2 = new int[ile];
	for (int i = 0; i < ile; i++)
	{
		cin >> tab1[i] >> tab2[i];
	}
	for (int i = 1; i <= ile; i++)
	{

		if (tab2[i-1] == 0 || tab1[i-1] == tab2[i-1]) cout << "1"<<endl;
		else
			cout << Newton(tab1[i-1], tab2[i-1]) << endl;
	}
	


	system("pause");
	return 0;
}

Co jest nie tak z tym kodem? U mnie jak testuje to działa, a SPOJ pokazuje ze bledna odpowiedź

[narbej]

Double są za mało dokładne i niepotrzebne.
Porysuj, pobaw się, samodzielnie, na papierze, trójkątem paskala i wyciągnij wnioski. Na pewno było już o tym w tym lub innym wątku, poświęconemu temu zadaniu.

PS
Wygląda, że tablice i indeksy opanowałeś do perfekcji, ale druga pętla jest “dziwna”
No i wklejanie kodu.

PS 2
Chodziło mi raczej o trójkąt newtona, ale jak zwał tak zwał, pobaw się.

[maruder1000]

Cześć,

mam klasyczny problem “u mnie działa, a mi nie zaliczają”…

Ideone.com

Ogólnie miałem taki pomysł, żeby policzyć dwumian Newtona lecz odpowiednio
skrócony, a by w założeniach komputer miał mniej do liczenia. Przeanalizujcie proszę
ten program i śmiało wytknijcie błędy.

[mariusz193]

problem klasyczny - więc zamiast pisać, może warto przeczytać wątek ?

powyżej znajdziesz dyskusję na temat poprawnego algorytmu, oraz przykładowe testy dla których twój program będzie dawał błędne wyniki

[misk]

Dzień dobry,
mam prośbę o pomoc w zadaniu. Wykonałem korzystając z trójkąta Pascala jednak sędzia wyświetla informację “Przekroczono limit czasu” Nie mam już pomysłu jak przyspieszyć wykonywanie programu. Do tej pory próbowałem to zadanie rozwiązać używając vector’a, pojedynczej tablicy, a teraz tablicy dwuwymiarowej z tym samym jednak skutkiem.

Kod przetestowałem na ideone (poniżej):

Ideone.com

[mariusz193]

mam prośbę o pomoc w zadaniu. Wykonałem korzystając z trójkąta Pascala jednak sędzia wyświetla informację “Przekroczono limit czasu”

a czego byś się spodziewał ?

dla maksymalnych danych będzie to:

10000 testów * (500000 dodawań + 1500000 dostępów do elementów tablicy)

czyli 5 mld dodawań i 15 mld dostępu do pamięci - to się zrobić szybko nie da

[misk]

Racja, dzięki za sugestię. Zmniejszyłem ilość działań i zadanie przeszło. Dzięki za pomoc

[grineee]

Uratowałeś mi życie, już miałem się poddać jak przeczytałem twoją odpowiedź i mnie olśniło, konkretnie tę część: “aby nie przekroczyć zakresu na zmianę odpowiednio mnożyć i dzielić”, jakoś mi to umknęło wcześniej, dzięki

Przy okazji bez używania jakichś newtonów czy trójkątów wyszedł mi całkiem ciekawy kod, mała próbka:
for (int j = u, x = 1; j > u-g; j--, x++)

[narbej]

Przy okazji bez używania jakichś newtonów czy trójkątów wyszedł mi całkiem ciekawy kod, mała próbka:

for (int j = u, x = 1; j > u-g; j–, x++)

A nie udziwniony? SPoj nie sprawdza jakości - czystości kodu a tylko kompiluje i prównuje dla konkretnych testów, wyniki programuu z przygotowanymi - wzorcowymi.

Np taki kawałek pętli:

for (int i{}, suma{}; i <100 and cout << i << " costam = "  << suma << endl; ++i, suma += i * i + suma*suma)

Myślisz, że to kawałek ciekawego, czy bardzo udziwnionego kodu? Nawet nie wiem czy i co on robi, mimo, że sam to naskrobałem '-)

No i nie jakichś, tylko bardzo konkretnych, i z punktu widzenia algorytmiki i matematyki kawałków wciedzy i pomysłów. Radze poszukać i poczytać, najlepiej np na wikipedi. Spróbować zrozumieć i zacząć stosować

[jasiu2012]

Cześć, dla parametrów (1000 2) w 16-stej linijce otrzymuje błąd informujący o dzieleniu przez zero. Próbowałem samemu analizować kod jednak nie dostrzegam niczego podejrzanego stąd moje pytanie jak naprawić ten błąd ?

Ideone.com

[quenthui]

Hej, przeanalizuj jakie wartości osiąga wywołanie silnia(1000)

[jasiu2012]

Zmieniłem podejście do problemu. Teraz program podaje wyniki jak należy lecz sędzią wciąż się czepia i zwraca błąd odpowiedzi…

Ideone.com

[quenthui]

Masz nieprawidłowy wynik dla:

30 15
32 16

prawidłowy out:

155117520
601080390

W razie czego, wyniki możesz weryfikować tutaj

[yula]

trochę za mało zmieniłeś podejście… za duże liczby ci wychodzą, pomyśl co można zrobić inaczej