[SPOJ] Przekroczono limit czasu

Question

Witam,

Po napisaniu programu, a następnie zgłoszeniu od sędziego otrzymuję wiadomość o przekroczeniu czasu oczekiwania (czy coś w ten deseń).

Nie wiem czy jest to błąd serwera czy może coś w kodzie jest źle (chociaż raczej wątpię). Tak naprawdę to dzisiaj zacząłem przygodę ze SPOJ i nie mam jeszcze w tym dużego doświadczenia.

Sprawdzałem również Sprawdź jeszcze, czy ktoś nie zadał już podobnego pytania:, ale tam nie znalazłem satysfakcjonującej mnie odpowiedzi.

Kod podam na wklejto.pl: http://wklejto.pl/718890

Treść do zadania można znaleźć tutaj: https://pl.spoj.com/problems/FCTRL3/

Prosiłbym o pomoc i o wyrozumiałość.

Answer 1

Zanim będziesz wysyłać kod sprawdź nie tylko przykładowe dane, ale również skrajne testy:

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

Twój wynik dla testu

IN:
1
1'000'000'000
OUT
0 1

Wynik silni z 1'000'000'000 nie zmieści się w żadnym typie liczbowym. Nawet jeżeli użyjesz jakichś własnych klas typu BigInt czas oczekiwania będzie zbyt długi. Weź funkcję liczącą silnie i sprawdź od czego zależą jej cyfry dziesiątek i jedności:

#include <iostream>

auto factorial(long long int num) -> long long int 
/* liczba w przypadku tego rekurencyjnego rozwiązania 
nie powinna być innego typu niż zwracany typ,
bo wtedy i tak podczas obliczeń zostanie dopasowany do typu 'num'
*/
{
	if (num <= 1)
	{
		return 1;
	}
	else
	{
		return num * factorial(num - 1);
	}
}

int main()
{
	for (int i = 0; i <= 20; ++i) 
    {
		std::cout << i << "!\t" << factorial(i) << "\n";
	}
}

W tym zadaniu tak naprawdę nie ma sensu liczyć silnii. 

W kodzie masz jeszcze kilka dziwnych pomysłów:

• zmienne globalne
• sprawdzanie poprawności testów - dane zawsze będą takie jak w treści zadania - nie musisz ich dodatkowo sprawdzać jeżeli nie zostało to ujęte w treści zadania
• wyszukiwanie ostatnich dwóch elementów stringa - można je od razu wypisać (oczywiście z odpowiednim warunkiem show.size() >= 2) jako show[show.size() - 2] i show[show.size() - 1]
• cin.ignore i jakieś getchary (tym bardziej) są zbędne. Chcesz zatrzymać działanie konsoli? Ustaw to w IDE. 
• zamiana liczby na string, aby obliczyć ostatnie cyfry - można użyć operacji modulo

PS. Do zapisywania dużych liczb jak np miliard użyj separatorów dziesiętnych. Będzie trudniej o proste błędy ;)

int number = 1'000'000'000;

Comments

Jeej, bardzo dużo rad, dziękuję z całego serduszka hehe 

---

cin.ignore(); getchar(); Jest dziwnym pomysłem, ale testerki i tak wejście podają z pliku więc jak nie ma błędów w czytaniu wejścia to i tak getchar() dostanie EOF i nie będzie na nic czekał więc to nie psuje niczego.

---

@Karol_Tesla Proszę ;)

@vector Nie sprawdzałem tego, ale dzięki za dopowiedzenie ;) Nie psuje to niczego, ale jest to trochę niewygodne, niepraktyczne i niekoniecznie może pełnić swoje zadanie w każdym przypadku.

---

Tak naprawdę to użyłem tego, ponieważ mój terminal pokazuje się na około 0.5 sekundy i nie wiem jakie są wyniki testów na terminalu. (Linux)

---

Kompilujesz i wywołujesz plik .out z terminalu?

---

Korzystam z Atom

Answer 2

Twój program działa za wolno, limit działania programu na tym zadaniu na spoju to 1s. Np dla n = 10^7 twój program działa dużo dłużej niż 1s.

 

auto foo (int liczba) ->  long long int
{
  
  if(liczba <= 1 ) return 1;
  else
  {  
    return liczba*foo(liczba-1);  
  }
  
}

Implementacja silni rekurencyjnie to jest zły pomysł bo dla n = 10^9 na stosie wyląduje co najmniej 3.72GIB pamięci zakładając ze adres powrotu funkcji zajmuje 4 bajty (pomijając już kwestie przekazywania argumentów, ramkę stosu i wyrównanie pamięci). Stos ma dużo mniejszy limit niż 3GB więc program wyrzuca SIGSEGV.

Liczenie całej liczby reprezentującej silnie to też jest zły pomysł ponieważ dla n >= 13 n! przekracza 2^31 czyli górny limit inta jaki może trzymać na większości architektur co daje niezdefiniowane zachowanie według specyfikacji języka c oraz c++.

Przed wysłaniem rozwiązań polecam je sprawdzać lokalnie wliczając w to skrajnie duże dane.

 

show = std::to_string(foo(n));

Nie widzę powodu aby konwertować liczby do ciągu znaków a później przeglądać tego ciągu znaków liniowo w poszukiwaniu ostatnich dwóch cyfr. foo(n) % 10 zwraca ostatnią cyfrę a foo(n) / 10 % 10 przedostatnią cyfrę.

 

if(1<=d && d <= 30) {
  // ...
  if( 0<=n && n <= 1000000000 ) {
    // ...
  }
}

Sprawdzanie poprawności danych na spoju i tego typu platformach jest w ogólności zbędne, możesz założyć że wprowadzone dane będą spełniały specyfikację z treści zadania.

 

int d, n;
std::string show;

W ogólności zmienne globalne są złe, ale powiedzmy że w rozwiązaniach zadań algorytmicznych są akceptowalne.

 

Co do podejścia algorytmu liczącego ostatnie dwie cyfry silni polecam zobaczyć sobie jak wygląda silnia dla n >= 10, to powinno pomóc w wymyśleniu znacznie wydajniejszego algorytmu.

Comments

Również bardzo Ci dziękuję! :)