21 / 59
Apr 2016

Rozwiązanie tego zadania nie wymaga w ogóle liczenia silni, to nie jest zadanie z zakresu wymyślania algorytmów czy ćwiczenia się w kodzie.
To zwykła ordynarna zagadka matematyczna. Do rozwiązania zestawem ifów albo jednym case'm czy switchem.
To co ktoś już napisał, należy udać się na stronę silni na wikipedii, albo samemu sobie na kartce rozpisać silnię do powiedzmy 10 i zauważyć pewną tendencję na pierwszym i drugim miejscu w liczbie, licząc od prawej,
Myślę, że już wystarczająco podpowiedziałem. Żadnego algorytmu, żadnych pętli, żadnego dzielenia, żadnego modulo. Z przykładu w zadaniu "Jeżeli wprowadzona liczba to 4, liczba dziesiątek to dwa, jedności to 4".

Bardzo mały fragment mojej dłuższej rozmowy na skype z aktywnym użytkownikiem SPOJA:

[10:41:08] mietko52: Jak czytam coś takiego, to:
[10:41:40] mietko52: 1. Scyzoryk otwiera mi się w kieszeni.
[10:41:52] mietko52: 2. Żygać mi się chce
[10:43:28] mietko52: 3. Odechciewa mi się myślenia o wymyślaniu nowych, czasami takich, a czasami lepszych zadań, bo po co, aby [potem] czytać takie komentarze?
[10:44:21] ..........: Jakie?
[10:44:22] mietko52: Oczywiście każdy ma prawo do swojego zdania, więc moje jest takie jak powyżej.
[10:44:45] mietko52: A sorrry:
[10:44:48] mietko52: http://discuss.spoj.com/t/496-tylko-dwie-cyfry-silni-a-problemow-100-silnia/11466/20
[10:45:34] mietko52: oraz tego samego mądrali: http://pl.spoj.com/problems/FCTRL3/#comments67

zostawiam to bez komentarzy.

Za to ja skomentuję.

Cały problem został doskonale przedstawiony w drugim linku. Pada tam następujące zdanie: "Jeżeli dobrze rozumiem [SPOJ] to jest strona mająca uczyć i wspomagać uczenie pisania algorytmów w różnych językach, a nie kółko do wyszukiwania sztuczek matematycznych". Pogrubiłem definicję SPOJa według autora tego zdania a słowo uczyć - jako najważniejsze w tej definicji i będące przyczyną frustracji - dowydatkowo wyróżniłem kursywą.

Dyskusja sprowadza się do filozofii - co to znaczy uczyć? Ostatnie dwie cyfry silni z pewnością są jakoś związane z nauką bo silnia to pojęcie matematyczne a matematyka jest nauką. Niestety tutaj pewniki się kończą. Nauka to szerokie pojęcie i nie sposób powiedzieć, czy wyznaczanie tych cyfr to coś bardziej matematycznego czy bardziej informatycznego (A może fizycznego, bo tam też są silnie? A może polonistycznego - bo czemu "silnia" a nie "ślńa" albo "factorial"?). Trudno powiedzieć, czy jest to zadanie łatwe, średnie czy trudne - bo niby jak to obiektywnie ocenić? http://pl.spoj.com/problems/AL_09_06/25 jest według mnie trywialne. Ale nim je rozwiązałem dziwiło mnie, że tak ciężkie zadanie jest w łatwych - na siłę szukałem tu dzikiego problemu teorii grafów i dopiero niedawno, po zdobyciu niemałej wiedzy o grafach, udało mi się to rozwiązać - po prostu przestałem tu szukać macierzy sąsiedztwa itd. bo zadanie jest elementarne. Trudno powiedzieć jak zadanie "Dwie cyfry silni" wiąże się z nauką nie tylko dlatego, że zależy to od poziomu trudności, ale też dlatego, iż nie da się łatwo powiedzieć co to znaczy "nauka". Chodzi o naukę rozumianą jako tworzenie nowej wiedzy nieznanej światu czy o naukę rozumianą jako zdobywanie wiedzy? A może obie opcje są prawidłowe?

Problem jest trudny i (po)ważny. Tak trudny i tak (po)ważny, że nadaje się na dysertację doktorską: http://www2.im.uj.edu.pl/phd/DymelPhd2009_pl.pdf14. Sam uważam, że poza Olimpiadą Informatyczną, Olimpiadą Fizyczną, Olimpiadą Matematyczną i może Olimpiadą Astronomiczną nie ma wartych uwagi Olimpiad w szkole średniej (ściślej: odradzam każdą). Nie jest to tylko moje zdanie - gdy byłem uczniem otwarcie odradzano mi udział w konkursach przedmiotowych a mój matematyk na studiach nie ukrywał swojego dość złego zdania o Olimpiadzie Matematycznej.

Załóżmy, że mówimy o algorytmice. Uznajmy ją za dział matematyki i zapytajmy się, w jaki sposób zadanie to wiąże się z algorytmiką. Z pewnością nie wymaga ono żadnego znanego (i nieznanego też) algorytmu. Niestety nie sposób stwierdzić, czy jest to wada czy też zaleta tego zadania. Może to być zaleta dla osoby nie lubiącej czytać o BFSach wszelakich, ale jest to zdecydowanie wada dla osób, które chcą poznawać algorytmy - w istocie zadanie jest dla nich beznadziejne i stanowi kompletną stratą czasu. Jest to zaleta dla początkujących, ale dużo takich zadań dekoncentruje bardziej zaawansowanych użytkowników. Wreszcie co to znaczy znać algorytmy? Czy znam algorytm Knutha-Morrisa-Pratta jeżeli wiem co on mniej więcej robi i do czego można go wykorzystać a przy tym nie umiem go zaklepać w danym języku albo nawet pseudokodzie w kilka chwil? Nie ukrywam też, że nie umiem udowodnić optymalności ani poprawności tego algorytmu. Nawet nie myślałem o tym by to udowodnić! A może wyrażenie "umieć algorytmy" oznacza odpowiedni sposób myślenia? Może chodzi tu właśnie o to by widząc problem w rodzaju "496. Dwie cyfry silni" być w stanie samemu wymyślić odpowiednie rozwiązanie? A może zadanie to jest błędne i prawidłowe rozwiązanie polega na wyprowadzeniu jakiejś funkcji (matematycznej a nie "programistycznej") nieznanej nauce, która dla danych argumentów podaje w jakiś mniej lub bardziej bezpośredni sposób ostatnie cyfry silni? Swoją drogą - co to jest silnia? Czy wiem co to silnia jeśli nie znam funkcji gamma? A tak w ogóle to może zamiast robić "bzdury" na SPOJu lepiej zacząć od problemu P vs NP?

Czas na krótkie podsumowanie.

Ludziska! SPOJ to tylko SPOJ! Nie szukajcie tutaj cudów bo wcale ich tu nie ma i nigdy nie będzie. Albo jakieś zadanie umiecie zrobić albo nie. Albo jakieś zadanie wam się podoba albo nie. Jeżeli uważacie, że zadanie jest bez sensu i nic wam nie da to po prostu nie rozwiązujcie go. Nikt wam też nie broni szukać rozwiązań w internecie - każdy programista sięga po dokumentację, każdy naukowiec przeszukuje książki i artykuły naukowe, każdy inżynier korzysta z norm, każdy lekarz konsultuje swoje wątpliwości z innym lekarzem, każdy maturzysta ma dostęp do tablic i może tam szukać wartości funkcji trygonometrycznych dla kąta 17 stopni... To tylko zadania i wielu ludzi nie rozwiązało żadnego problemu na SPOJu a są oni dobrymi programistami / naukowcami / nie-wiadomo-kim-jeszcze. Z pewnością są też tacy, którym SPOJ po prostu się nie podoba i wolą inne strony z zadaniami. Wielu analizuje jedynie materiały z olimpiad informatycznych. Sam mam ochotę powiedzieć coś niemiłego o http://pl.spoj.com/problems/HANG/26, ale nie zamierzam niczego zarzucać autorowi, który po prostu stworzył zadanie opisane mniej lub bardziej poprawnie i jednoznacznie. Wielu ludzi podołało temu zadaniu, ale ja nie. I nie czuję się przez to gorszy ani nie uważam że autor zadania jest głupi ani nie sądzę, że to zadanie jest bez sensu! Zwyczajnie nie podejmuję entej próby rozwiązania. Może kiedyś, ale teraz wolę robić zadania średnie i poznawać nowe algorytmy a nie bawić się z wisielcem. Jeżeli więc coś wam się nie podoba w danym zadaniu to zwyczajnie go nie rozwiązujcie. Przypominam, że na SPOJu nie ma gwarancji poprawności zadań ani gwarancji nauczenia się czegokolwiek. SPOJ to po prostu SPOJ. Osobiście traktuję go jako fajną rozrywkę intelektualną. Może też tak powinniście zrobić?

Przepraszam, jeżeli to spam.

10 months later

Witam, mam problem dotyczący zadania. Chyba nie mogę wklejać kodów źrółowych do poprawnych rozwiązań, więc tylko opiszę o co mi chodzi. Mianowicie próbuję zoptymalizować rozwiązanie, żeby program zużywał jak najmniej pamięci i... bez skutku. Patrząc na rozwiązania innych użytkowników dla C++ widzę wyniki rzędu 2M, mój program to 15M, bez różnicy jak go rozplanuję. Próbowałem do liczenia silni funkcji rekurencyjnej, pętli for oraz rozwiązania w ogóle bez liczenia silni, z wykorzystaniem samych warunków i cały czas nie mogę zejść poniżej tej magicznej granicy. Jestem początkujący, ale interesuje mnie co mógłbym z tym zrobić, może problem dla większości trywialny, ale jak na razie nie dla mnie :slight_smile:

Załóż, że nie masz na to wpływu - i faktycznie tak jest. Jak już tak koniecznie chcesz porównywać z innymi zgłoszeniami, to porównuj też datę zgłoszeń, wersję kompilatora itd. Kiedyś były inne czasy, inny sprzęt, inne kompilatory [wersje] inne ustawienia opcji kompilacji itd. Teraz to wszystko buja w obłokach i chmurach, a pamięci jest od za....trzęsienia i nikt nie będzie się przejmował jakimiś marnymi 15 Mb w tą czy w tamtą stronę. :wink:

PS
nikt == admini SPOJ'a

Dobra, skoro tak mówisz to się nie będę tym na razie przejmował :slight_smile: zdziwiło mnie tylko, że stosując funkcję rekurencyjną osiągnąłem taki sam wynik co stosując pętlę, ale pewnie różnica jest widoczna dopiero przy większej ilości operacji, w sumie tutaj w rekurencji to tylko 10 wywołań maksymalnie, także ilość nie powala pewnie, żeby zrobić jakąkolwiek różnicę. Dzięki za szybką odpowiedź :wink:

Inaczej. Na dzień dobry dostajesz minimum (np ~15 Mb dla CPP14). Jeżeli wystarczy Ci mniej, to i tak zostanie 15. Jak potrzebujesz więcej to dostaniesz więcej, ale nie nieskończoność: http://pl.spoj.com/ranks/FCTRL3/lang=CPP14,start=86213
Gdy się będziesz przesuwał w lewo [klikając w numerki stron 45, 44, 43 .....], znajdziesz taki dzień, w którym nastąpiła zmiana.

3 months later

Cześć, nadszedł i mój czas zmierzenia się z tym potworkiem, napisałem już 3 algorytmy wszystkie pozornie prawidłowe. Poniższy jest najprostszy i najbliższy odpowiedzi, ale nie mam najmniejszego pojęcia dlaczego sędzia nie chce mi dać AC

Docenię każdą, chociażby najmniejszą podpowiedź

Z treści zadania:

...Liczbę n! (czytaj n-silnia) definiuje się następująco. Jeśli n ≤ 1, to n! = 1. ....

i dalej:

Opis każdego przypadku składa się z jednej linii, w której znajduje się jedna nieujemna liczba całkowita n (0 ≤ n ≤ 1 000 000 000).

Dziękuję czasem ciężko wziąć nic pod uwagę :slight_smile: pozdrawiam i dziękuję

2 months later

jak dla mnie to czy nie powinna być używana w tym zadaniu rekurencja która przekracza czas wykonania zadania a przechodzi najgłupsza konstrukcja z ifów ?

Jak dla mnie, nie [koniecznie].

PS
O mądrości lub głupocie konstrukcji decyduje konstruktor [coder].

PS 2
Dla SPOJ’a liczy się tylko uzyskany w rozsądnym czasie wynik, a nie metoda. Możesz więc spokojnie użyć zamiast: “najgłubszej konstrukcji z [kilku] ifów”, dowolnej innej, np ze switch, z jednym ifem, lub całkowicie bez, a także możesz to zrobić, jak tylko sobie pomyślisz, czy rekurencyjnie czy iteracyjnie czy jeszcze inaczej. Masz tu całkowitą swobobę, liczy się cel a nie środki.

Jeżeli jesteś w stanie zaproponować sensowne rozwiązanie rekurencyjne dla tego problemu to dlaczego nie? Sytuacja jest o tyle prosta, że sensowne rozwiązanie oznacza jedynie AC czyli ma wyłącznie mieścić się w jakimś limicie czasowym i działać zaledwie dla wybranych, podanych w treści zadania liczb. A jeżeli będzie ono lepsze od ifów to chętnie je poznam.

1 year later

Witam, co tu może być nie tak? Prosze o rade :smiley:
Z góry dziękuje!

Masz zły wynik dla pewnej bardzo małej wartości. Polecam wikipedię/google i poczytanie o silni :slight_smile:

Droga Spolecznosci,
rozpoczynam swoje kroki w jezyku Java. Przewertowalem forum, wdrozylem wiele podpowiedzi nie mnie jednak wciaz sedzia wyswietla informacje o przekroczonym limicie czasu. Czy ktos bylby tak mily i pomoglby mi znalezc przyczyne? Z gory bardzo dziekuje!

Coś słabo czytałeś. Ile zajmie ci wykonanie programu dla tego testu?
10
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Poza tym twój program daje złe wyniki: https://ideone.com/c7ZvlY5

Wie ktos dlaczego to nie dziala?