Siemanko. Zauważyłem, że na trello jest do zrobienia tutorial na temat SPOJA, algorytmów. To postanowiłem, że zrobię.
Może zacznę do czego służy SPOJ i platformy tego typu. Służą one by rozwijać myślenie oraz jak by pisać optymalny kod, a nie pisanie ładnego kodu.
Na start radzę wam się zaznajomić z takimi jak pojęciami jak: złożoność obliczeniowa i notacja O. Pokrótce omówię te pojęcia ale i tak radzę poczytać na google o nich.
Złożoność obliczeniowa - jest to pojęcie jak długo się wykonuje program lub jak dużo pamięci zużywa. Na przykład jeśli mamy program i on wykonuje 2 zagnieżdżone pętle i jeszcze jakąś pętle ( nie jest ona zagnieżdżona ). To złożoność obliczeniowa będzie tych dwóch pętli zagnieżdżonych.
Notacja O - jest to sposób zapisu złożoności obliczeniowej. Biorąc przykład z góry to w przypadku notacji O będzie O ( n^2 ).
Wiem, że jest to zagmatwane ale dam kilka przykładów ( pseudo kod i zapis w notacji O ) i się może rozjaśni.
int n = 150550;
for ( int i = 0; i < n; i++ ) cout<<i
Tutaj wykonuję jedną pętlę i złożoność wynosi O(n)
int n = 15091421 // te wartości mogą się zmieniać
int m = 151421413 // te wartości mogą się zmieniać
for ( int i = 0; i < n; i++)
for ( int j = 0 j < m; j++) cout<<i+j;
Hmm złożoność to O ( n*m ) bo w każdym obiegu pętli wykonuję drugą pętlę
cout<<"ala ma psa"
No tu będzie szok złożoność wynosi O ( 1 ). Wykonuję stałą liczbę operacji ( przy każdym uruchomieniu programu ta liczba operacji się nie zmieni).
int n = 154231431 // może ta wartość się zmienić
for ( int i = 0; i * i < n; i++)
for ( int j = 0; j < 15; j++) cout<<i+j;
No tutaj trochę się rozpiszę. Na początku pomyślicie, że złożoność O ( sqrt ( n) * 15 ). Myślicie dobrze ale przyjeło się, że stałą liczbę operacji pomijamy ( druga pętla zawsze będzie wykonywać 15 kroków ). Czyli złożoność wynosi O(sqrt(n)) <- te 15 pomijamy
Dobra główna kwestia skończona. Przejdźmy do kwestii jak się takie zadania pisze, bo jak widzę jak to próbujecie rozwiązać to ręce opadają.
Kod piszemy jak najprościej. Czyli bez używania klas, wskaźników, tablic dynamicznych takich bajerów <- w przypadku SPOJA i innych konkursów, portali jest to ZŁE. Za to jak piszemy, jak najprościej, tablice deklarujemy poza mainem i na sztywno maksymalną ilość danych ( trochę niejasno ale zaraz podam przykład ). Zamiast pisać swoje struktury danych to upewnijcie się, że nie ma ich w STL.
Przykład poprawny
#include <iostream>
using namespace std;
// przykład poprawny do zadania "tablice" na SPOJ
int tab[100]; // w zadaniu jest napisane jasno maksymalna ilość danych to 100 liczb
int t, n; /// liczba testów i liczba danych tablicy
void wypisz (int z){
for ( int i = 0; i < z; i++ ) cout<<tab[i]<<endl;
// nie używamy żadnych wskaźników do tablicy
}
void podaj ( int z ){
for ( int i = 0; i < z; i++ ) cin>> tab[i];
}
int main() {
cin >> n;
for ( int i = 0; i < n; i++ ){
cin >> t;
podaj ( t );
reverse ( tab, t);
wypisz(t);
}
}
Przykład niepoprawny
#include <iostream>
using namespace std;
// Przykład niepoprawny rozwiązywania zadań
void wypisz (int* tab, int z){
for ( int i = 0; i < z; i++ ) cout<<tab[i]<<endl;
// bawimy się jakimiś wskaźnikami i utrudniamy sobie życie bo łatwo można się pomylić
}
void podaj ( int* tab, int z ){
for ( int i = 0; i < z; i++ ) cin>> tab[i];
}
int main() {
int n;
cin >> n;
for ( int i = 0; i < n; i++ ){
int t;
cin >> t;
int *tab = new int [t]
podaj ( t );
reverse ( tab, t);
wypisz(t);
}
}
Przykłady raczej są do poprawy bo po prostu słabo obrazują o co mi chodzi.
Jak wypisujemy dane. Istnieją dwie możliwości( online i offline ). Online polega, że po otrzymaniu danych jesteśmy wstanie wypisać wynik np jak w zadaniu tablice, dostajemy tablice, odwracamy i wypisujemy. Wypisywanie Offline polega na zmagazynowaniu wszystkich danych i je wypisaniu po obliczeniu wszystkich testów, czyli w przeciwieństwie do online wczytujemy wszystkie podane tablice i je odwracamy, a następnie wypisuje po kolei.
Co do wypisywania danych ma być ząb w ząb podany wynik na przykładzie do zadania ( na samym dole zadania są podane testy przykładowe i odpowiedzi do nich ).
Dobra wysłałem zadanie i dlaczego SPOJ mnie nie lubi ?
Popularne komunikaty z SPOJ
wrong answer/ zła odpowiedź- no tu nasz program podał złą odpowiedź, może się zdarzyć, że źle wypisaliście dane.
compilation error / błąd kompilacji - co tu dużo mówić, program się na sprawdzaczce nie skompilował i dał error.
time limit exceeded / przekroczono limit czasu- tutaj jest trochę ciekawe. Bo wasz program jest za wolny czyli program nie jest zoptymalizowany ( da się lepiej rozwiązać) .
Tutaj nie jestem pewien czy takie błędy wyskakują na SPOJU, ale na pewno wyskakują w szanujących się sprawdzaczkach
naruszenie bezpieczeństwa - wykonujemy takie operacje które pytają system o czas lub coś podobnego. Może się to zdarzyć gdy naruszymy limit pamięci przeznaczony na program lub wyjechaliśmy poza zakres tablicy.
Chyba wszystkie sprawdzaczki mogą nie wypisać żadnego błędu z wyżej wymienionych, a napiszą np error501. Takie błędy trzeba już wygooglać i przeczytać o co chodzi bo są to bardzo specyficzne błędy.
Chyba wszystkie potrzebne rzeczy na start przekazałem. Błędy na pewno są to proszę pisać i będę poprawiał. Uwagi, pytania z chęcią odpowiem. Jeśli na coś wpadnę to dopiszę
