496. Tylko Dwie cyfry silni, a problemów 100! [‘!’ = silnia] ;-)

dudiic96 · Mar '17

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

narbej · Mar '17

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ę.

PS
nikt == admini SPOJ'a

dudiic96 · Mar '17

Dobra, skoro tak mówisz to się nie będę tym na razie przejmował 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ź

narbej · Mar '17

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.

parolityk · Jun '17

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ź

narbej · Jun '17

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).

parolityk · Jun '17

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

ccoder · Sep '17

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 ?

narbej · Sep '17

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.

tarpauwatratar · Sep '17

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.

micsiw663 · Dec '18

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

eksekk · Dec '18

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

micsiw663 · Dec '18

Dzięki za pomoc! Pozdrawiam

warriortm · Dec '18

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!

import java.util.*;
public class silnia {

public static void main(String[] args) {
	int n;
	int n2 = 1;
	int d;
	long k = 1;
	Scanner in = new Scanner(System.in);
	d = in.nextInt();
	if(d > 0 && d < 31) {
	for(int i = 0; i < d; i++) {
		k=1;
		n2=1;
		n = in.nextInt();
		if (n<0) {break;}
		if(n == 0) {System.out.println("0 1");
		}else if (n <1000000001) {
		for(int j = 0;j < n; j++) {
		k = k * n2;
		n2++;
		}System.out.println(k/10 + " " + k % 10);}
		
	}}}
			
			
		}

eksekk · Dec '18

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

sajmonn · Dec '18

Wie ktos dlaczego to nie dziala?

mariusz193 · Dec '18

poczytaj, jak działa operacja dzielenia

sajmonn · Dec '18

Chodzi mi bardziej o to ze w ideone dziala a u sedziego nie

mariusz193 · Dec '18

działa dla niewielkiego zakresu wejścia - to że test z zadania daje poprawny wynik, to za mało

sprawdź wynik np. dla:

1
100

sajmonn · Dec '18

Wyszlo “0 8” ale srednio mam gdzie sprawdzic poprawnosc tego poniewaz jest to ogromna liczba.
Czy python moze w zmiennej przechowywac tak duza liczbe?

share a link to this topic