833. Dwumiany [BINOMS]

[ajron]

Hej!

Mam problem z zadaniem wyżej ( http://pl.spoj.com/problems/BINOMS/ ), w czym rzecz... otóż napisałem program do obliczenia Symbolu Newtona, wyniki w testach dostaję dobre lecz gdy wysyłam do sędziego to odsyła mi błąd SIGFPE - z tego co wyczytałem to ten sygnał powiadamia o błędnym działaniu arytmetycznym. Nie wiem za bardzo co tu pozmieniać, bo ani nie dzielę przez zero, (jedyne gdzie dzielę to na końcu ale tam nigdy zera nie będzie, bo 0! = 1), ani nie wyciągam pierwiastka stopnia parzystego z liczby ujemnej, k i n sa liczbami nieujemnymi, k<=n zatem nigdy ujemna silnia nie wyjdzie... nie mam pomysłu.
Podsyłam kod:
ciach!

A już tak swoją drogą, da się jakos zsychronizować konto z PL SPOJa (http://pl.spoj.com/users/ajron/) z tym drugim, które się utworzyło z automatu chyba (http://www.spoj.com/users/ajron/)? Bo troche zawartość tego drugiego słabo wygląda.

[j4rooo]

Ok, dostajesz SIGFPE, który występuje gdy dzielisz przez zero lub gdy dzielisz modulo przez 0. Dzielenie masz tylko w jednym miejscu, więc funkcja factorial musi zwracać 0. Oczywiście patrząc na nią, możemy mieć wątpliwości, że to możliwe, ale wystarczy sobie przypomnieć o przepełnieniu i staje się to możliwe Musisz sprytniej podejść do tematu, tak aby nie osiągać tak dużych liczb, aby wystąpiło przepełnienie.

[narbej]

da się jakos zsychronizować konto z PL SPOJa (http://pl.spoj.com/users/ajron/) z tym drugim, które się utworzyło z automatu chyba (http://www.spoj.com/users/ajron/)? Bo troche zawartość tego drugiego słabo wygląda

Nie, ale można "łatwo" poprawić wygląd tego drugiego. Wystarczy zacząć rozwiązywać zadania na: http://www.spoj.com/problems/classical/
Małą pomocą może być ten wątek: http://pl.spoj.com/forum-old/viewtopic.php?f=1&t=1992&sid=ad13349f90c861ed88a39f84ef62e7f4

PS
Kody swoich programów wklejaj raczej za pomocą: http://ideone.com/

PS 2
Np taki lub tego, podobnego typu testy:
1000 998

[ajron]

j4roooo, z przepełnieniem to możliwe... chyba jedyny powód. Nie wiem tylko jak wpaść na lepsze rozwiązanie, wiesz jak to jest jak wpadniesz na jakiś pomysł - trudno od niego odejść. ; p Może przy liczeniu silni następować przepełnienie, muszę na to sposób znaleźć, rekurencyjnie odpada bo to chyba wolniejsze niż iteracyjnie. Przysiądę do tego jutro i spróbuję rozwiązać. Dzięki za uświadomienie.
narbej, dzięki za wyjaśnienie. Szkoda, że nie da rady zsynchronizować konta, ew. nie istnieje jedno konto "globalne".

[j4rooo]

Pewnie nie znasz tej matematycznej sztuczki. Tak co znasz to:

(a+b+c)-(d+e+f) = a - d + b - e + c -f

a teraz sprawdź czy z mnożeniem i dzieleniem to też tak działa

[ajron]

Musiałem się odmódżyć po algorytmie szyfrującym przy Neverwinter Nights 1... ale wracając!
Napisałem takie coś:
ciach!
Outputy są prawidłowe, jak wysyłam do sędziego to odsyła mi błędną odpowiedź.
To przez to, że zmienna automatyczna jest typem zmiennoprzecinkowym? Na końcu rzutuję ją na inta. : p

[j4rooo]

W moim AC też rzutuje ale long doubla. Sprawdź np. przypadek

1
500 500

Mi daje:

1

Poza tym, ja rzutuje zawsze przez zwykły operator rzutowania. Jakoś nigdy nie miałem chęci się nauczyć czym się te wszystkie casty różnią Jeśli dalej nie przejdzie to daj znać.

[ajron]

Dla testu

1
500 500

zwraca mi wynik 1, czyli dobry. Z rzutowaniem C: (int)wynik / int(wynik) nie działa również, już trochę nie mam pomysłu na zadanie, pierwszy raz : p

[j4rooo]

Głównie o long double chodziło, ale nie pomaga.

Na ideone (więc i na spoj) zwraca 0 dla 500 500:
http://ideone.com/Zygflz

Ale oczywiście nie wiem czy jest taki test.

[ajron]

W tym co wysłałeś ciach! wysyła zero, czyli źle, bo dla n=k powinno zwracać jeden, co jest logiczne, bo istnieje tylko jedna taka kombinacja. Jak zamienisz na ciach! to zwraca dobrze z tym, że i tak na SPOJu zwraca mi WA...

[j4rooo]

Byłem zobaczyć na starym forum: http://pl.spoj.com/forum-old/viewtopic.php?f=1&t=1288 różnie tam piszą, ale mam wątpliwości czy mój AC kod, który swoją drogą trochę już ma, nie miał czasem dużo szczęścia, że przeszedł na zmiennoprzecinkowych Dla wielu testów, które tam są mam inny wynik.

Różnica w algorytmie, którą masz teraz u siebie polega na tym, że najpierw mnożysz duże liczby (od n w dół) a dzielisz przez małe od (od 1 do k). Zmień kod tak, żeby zarówno n i k rosły lub malały jednocześnie i powinieneś mieć AC. Albo przeczytaj stary wątek i spróbuj podejść inaczej do tematu.
Dla

1
100 95

Powinieneś mieć

75287520

[ajron]

Zaliczyło, przed pętlą po prostu wrzuciłem warunek będący własnością Symbolu Newtona. Z góry dzięki j4rooo za pomoc, dobranoc!

[dziabagooo]

Witam,

Przekroczono limit czasu…

Co z tym, mozna zrobic?

Ideone.com

[narbej]

Przekroczono limit czasu…

Co z tym, mozna zrobic?

Nic, czasu nie da się zatrzymać niestety

BTW
Na ideone można i należy wklejać testy: i testować, testować, testować [nie użyłem copy paste ;-)]
https://ideone.com/DUT0A1 <-- 0.48 sek
https://ideone.com/O1jFqP <-- TLE [ale podejrzewam, że dodatkowo wynik byłby zły dla drugiego przypadku - 1000 995]

BTW 2
A jednak coś się da zrobić Czytać, czytać, czytać [też bez copy paste ;-)] Nawet na wikipedi o dwumianach czy binomials, umiesz chyba posługiwać się jakąś wyszukiwarką?

BTW 3
Dodatkowo, proponuję i zachęcam do zapoznania się z wątkiem: JZLICZ C++ na CodeBlocks dziala, judge odrzuca. Możliwe, że właśnie jesteśmy świadkami historycznej chwili, powolnego zaniku-zamierania bezinteresownej pomocy na SPOJ’u i na forum