POLSKI SPOJ

Ze SPOJem za pan brat?

Tutorial ten wyjaśnia jak używać SPOJa. Po przeczytaniu poniższego tekstu, współpraca ze SPOJem będzie czystą przyjemnością :)

Rejestracja i profil

Aby się zarejestrować kliknij tu. Sądzę, że przeznaczenie pól rejestracji jest łatwe do odgadnięcia. Poniżej znajduje się opis dwóch z nich:

• Wysyłaj potwierdzenia zgłoszeń e-mailem: - zaznacz to pole, jeśli chcesz otrzymywać e-mailem informacje o statusie swoich rozwiązań (po wysłaniu każdego zgłoszenia). Wiadomość będzie zawierac numer zgłoszenia (unikatowy w systemie SPOJ), nazwę problemu, którego dotyczy zgłoszenie oraz rezultat wykonania (wraz z krótkim opisem ewentualnych błędów).

• Domyślny język programowania - pozwala Ci wybrać, który język domyślnie będzie zaznaczony przy nadsyłaniu rozwiązań (ustawienie to jest nadpisywane, gdy przed chwilą wysłałeś rozwiązanie w innym języku, lub gdy problem, który próbujesz rozwiązać, nie zezwala na zgłaszanie rozwiązań w języku wybranym przez ciebie jako domyślny)

Główny SPOJ, kontesty oraz SPOJ w innych językach

Tutorial ten bazuje na polsko-języcznej wersji SPOJa, ale SPOJ posiada również inne wersje: Wietnamską, Brazylijską, Kirgijską i Angielską. Co więcej, SPOJ hostuje wiele kontestów organizowanych przez różnych ludzi, szkoły, uczelnie i organizacje; niektóre kontesty są publiczne i każdy może w nich uczestniczyć. Poruszanie sie po kontestach jest bardzo podobne do poruszania się po głównym SPOJu.

Wybór problemu do rozwiązania

Wybranie pierwszego problemu do rozwiązania jest... trudnym zadaniem dla początkujących użytkowników, gdyż SPOJ daje Ci dostęp do bardzo rozbudowanego zbioru zadań. W chwili obecnej najlepszym miernikiem trudności problemów jest liczba użytkowników, którzy go rozwiązali oraz procent zaakceptowanych rozwiązań (w niedalekiej przyszłości powstanie system otagowwyania zadań, który pozwoli na kategoryzowanie problemów i umożliwi wygodne ich wyszukiwanie). W zależności od twoich umiejętności i doświadczenia, możesz wybrać zadania prostsze lub trudniejsze - każdy znajdzie coś dla siebie.

Zadania są obecnie podzielone na cztery kategorie:

• łatwe - zadania dla początkujących użytkowników
• średnie - problemy o średnim poziomie trudności
• trudne - zadania trudne i problemy z niestandardowymi algorytmami rozwiązania
• wyzwania - zadania, których wynikiem jest pewien przedział punktowy

Aby podejrzeć zbiór zadań, kliknij pozycję menu "zadania" z lewej strony.

Kolumna ROZW pokazuje ile użytkowników rozwiązało dany problem. Kolumna AKC % udostępnia informacje o tym jaki procent zgłoszeń został zaakceptowany.

Nadsyłanie rozwiązań

Zerknijmy na przykładowy problem na SPOJu o nazwie Harry and big doughnuts (Harry i duże pączki)
DOUGHNUT

Każde zadanie składa się z:

Opisu problemu:

Młody Harry został poproszony o kupienie karmy dla kotów przez swoją sąsiadkę - starą, dziwną panią, która była właścicielką wielu kotów. Ale koty też były dziwne i jadały tylko pączki. Toteż sąsiadka chciała aby (...)

Opisu wejścia:

W pierwszej lini jedna dodatnia liczba całkowita t (t <= 100) oznaczająca ilośc testów (Harry został poproszony o kupno pączków kilka razy). Następnie t lini (...)

Opisu wyjścia:

t lini zawierających słowo "yes" jeśli Harry jest w stanie wykonać zadanie lub "no" jeśli pączki złamałyby Harremu kręgosłup.

Przykładowego wejścia:

3
5 15 3
1 5 4
13 25 2

Przykładowego wyjścia:

yes
yes
no

Dodatkowych informacji:

Dodane przez - autor zadania
Data dodania - mówi samo za siebie :)
Limit czasu wykonania programu - jak długo program może wykonywać obliczenia; jeśli program nadesłany przez ciebie nie zakończy się w wyznaczonym czasie, otrzymasz rezultat "przekroczono limit czasu"
Limit długości kodu źródłowego - jak wielkie może być nadesłane przez ciebie rozwiązanie (w bajtach)
Języki programowania - w jakich językach można nadsyłać rozwiązania dla danego problemu

Dane wejściowe i wyjściowe używane przez SPOJowego sędziego do weryfikacji poprawności twojego rozwiązania są wybierane przez problem-settera (osobę dodającą problemy) i nie są widoczne dla nikogo poza nim. Wiele trudniejszych problemów posiada podchwytliwe dane testowe, toteż umiejętność tworzenia własnych i kompleksowych zestawów testowych na pewno Ci się przyda. W chwili obecnej nie ma możliwości testowania swoich rozwiązań online z własnymi danymi testowymi (interaktywnie lub nie) ale planujemy wprowadzić tę funkcjonalność w niedalekiej przyszłości.

Jeśli sądzisz, że zadanie ma niepoprawne dane testowe lub jego opis nie jest jasny, odwiedź forum oalbo umieść komentarz na dole strony z problemem. Gdy umieszczasz komentarz, zatosuj się proszę do poniższych reguł:

1. Nie nadsyłaj tutaj żadnego kodu źródłowego!
2. Zamieszczaj proszę krótkie uwagi i komentarze; nie spamuj!
3. Szerszą dyskusję (wskazówki, pomysły, rozwiązania) znajdziesz na forum.
4. Autorzy zadań mogą usunąć lub ukryć dowolny komentarz oraz mogą zamieszczać kod w html-u (np. w celu udostępnienia odsyłaczy).

Aby napisać rozwiązanie, użyj własnego edytora bądź IDE.

Teraz spróbujmy rozwiązać zadanie DOUGHNUT.

Poniżej zamieszona jest analiza problemu i rozwiązania do niego, więc jeśli chcesz zrobić to zadanie samodzielnie, napisz rozwiązanie i wtedy wróć do tutoriala :)

Po przeczytaniu opisu problemu dowiadujemy się, że musimy pomóc Harremu... Ale dla nas najważniejsze jest znaczenie liczb: c, k oraz w.

Stara pani posiada c kotów, zatem Harry musi kupić c pączków. Każdy pączek waży w kilogramów. Harry może udźwignąć tylko k kilogramów. Podejrzewam, że już wiesz jak powinno wyglądać rozwiązanie... :)

Przykładowy kod w C++

Początek:

#include <cstdio>
 
 
int main() {
 

Zmienne:

t - ilość testów
c, k, w - dane problemu

Opis problemu podaje, iż każda liczba jest mniejsza lub równa 100, zatem typ integer (32 bity) jest wystarczająco duży do wszystkich kalkulacji (nawet short integer (16 bitów) by wystarczył).

	int t, c, k, w;
	

Czytanie wejścia i reszta kodu:

	scanf("%d", &t);
	while(t--) {
		scanf("%d %d %d", &c, &k, &w);
HERE GOES THE MAIN LOGIC

	}
 
	return 0;
}
 

Głowna logika:

		if(c*w <= k)
			printf("yes\n");
		else
			printf("no\n");

Aby wysłać rozwiązanie, kliknij link zgłaszanie i albo wklej kod źródłowy rozwiązania do pola tekstowego, ablo załaduj kod z pliku. Następnie wybierz język rozwiązania i wciśnij przycisk Wyślij.

Zostaniesz przekierowany do strony statusu, gdzie możesz podejrzeć postęp oceniania twojego zgłoszenia. Po kilku chwilach zobaczysz rezultat:

• AC - zaakceptowano - twoj program wykonał się poprawnie i zwrócił prawidłową odpowiedź
• WA - błędna odpowiedź - twój program wykonał się poprawnie, ale zwrócił nieprawidłową odpowiedź
• TLE - przekroczono limit czasu - twój program skompilował i uruchomił się w prawidłowy sposób, ale nie zakończył działania w wyznaczonym czasie
• CE - błąd kompilacji - nie udało się skompilować twojego kodu. Zauważ, że tylko niektóre języki mogą zwrócić CE - błędy składniowe w językach interpretowanych mogą po prostu prowadzić do WA (Python, Perl)
• RE - błąd czasu wykonania - twój program skompilował się, ale zakończył działanie w nieprawidłowy sposób. Możliwe sygnały błędów:
  - SIGSEGV (signal 11) - najczęstszy, "segmentation fault" - np. indeks poza tablicą
  - SIGXFSZ (signal 25) - program wygenerował za dużą ilość danych
  - SIGFPE (signal 8) - "floating point error" - np. dzielenie przez zero
  - SIGABRT (signal 6) - błąd zgłaszany "osobiście" przez program - zdarza się np. w C++ STL
  - NZEC (non-zero exit code) - pozwala na rozróżnienie wywalenia się programu i nieprawidłowej odpowiedzi w językach interpretowanych
  - inne - istnieją również inne sygnały mogące spowodować załamanie się działania programu - pokazywane są jako "inne"

Mam nadzieję, że udało ci się otrzymać AC za pierwszym razem. Jeśli nie - nie szkodzi; możesz nadsyłać rozwiązania dowolną ilość razy.

Teraz, gdy już rozwiązałeś swój pierwszy problem, powinieneś być gotowy do stawienia czoła SPOJowi! :)

Kod źródłowy twoich rozwiązań

Historia nadsyłanych przez ciebie rozwiązań jest dostępna z twojego profilu (moje konto -> historia zgłoszeń). Aby sprawdzić kod źródłowy twojego rozwiązania, kliknij numer ID zgłoszenia na liście zgłoszeń (tzn. na stronie statusu, historii zgłoszeń albo gdy przejdziesz na stronę problemu i klikniesz Moje zgłoszenia, Wszystkie zgłoszenia, Najlepsze). Kod źródłowy twoich zgłoszeń jest widoczny tylko dla ciebie.

Ranking

Każdy z uczestników może zobaczyć swój dorobek punktowy w rankingu.

Punkty za rozwiązanie zadania przydzielane są w zależności od kategorii zadania:

• łatwe: 1 pkt,
• średnie: 2 pkt,
• trudne: 3 pkt,
• challenge: (wynik_najlepszy / wynik_Twojego_programu) * 4 pkt, ponadto za najlepsze rozwiązanie przyznawany jest dodatkowy punkt (lub odwrotnie dla problemów maksymalizacyjnych).

Jak ściągnąć wszystkie problemy jednym kliknięciem?

Przejdź do listy zadań, zaznacz Typ dokumentu i kliknij w link książeczka.

Ograniczenie czasu i pamięci dla rozwiązań

Limit pamięci dla każdego problemu na SPOJu wynosi 256MB. Limi czasu dla zestawów danych testowych w zadaniach może być różny. Jeśli limit czasu wynosi 3 sekundy (informacja znajduje się na dole strony zadania), możesz założyć, że limit czasu dla każdego zestawu testowego to 3 sekundy. Jeśli limit to 1-3 sekundy, możesz założyć, że w zadaniu jest kilka zestawów testowych: najkrótszy limit to jedna sekunda, zaś najdłuższy to 3 sekundy.

Więcej...

Po pomoc, więcej informacji i wskazówki odwiedź nasze forum (FAQ znajduje się na forum).
Zajrzyj też na stronę zasady.

Powodzenia!