Wersja dla języka C++

System oceniania na OIJ jest całkowicie zautomatyzowany. Z użyciem takiego systemu wiążą się niewątpliwe zalety: szybkość, zaufanie, jednolitość kryteriów i wiele innych, jak również kilka wad. Jedną z nich jest bardzo “brutalna” ocena rozwiązań zawierających choćby drobne pomyłki. Intencją tego poradnika jest wytłumaczyć Ci w jaki sposób przygotować swoje rozwiązania, aby uzyskana punktacja odzwierciedlała poprawność pomysłu i umiejętności implementacyjne. Poradnik przestrzega przed niektórymi popularnymi pułapkami i problemami, rekomendujemy jego przeczytanie w całości.

Rozwiążemy przykładowe zadanie Liczby Fibonacciego. Treść zadania można zobaczyć tutaj. Zadanie, choć niezbyt ciekawe, ma wiele poprawnych i niepoprawnych rozwiązań. Jeszcze raz zachęcamy wszystkich Czytelników do przejrzenia dokumentu w całości, nawet jeżeli potrafią z łatwością rozwiązać to zadanie.

Po zrozumieniu tego samouczka, rekomendujemy przygotowanie własnego rozwiązania i wysłanie go do systemu SIO2. W konkursie testowym znajduje się jeszcze kilka innych, bardzo prostych zadań. Rozwiązanie zadań w konkursie testowym nie jest wymagane, nie przynosi też żadnych punktów do kwalifikacji do kolejnych etapów zawodów, ale pozwala upewnić się, że reguły zawodów i sposobu oceny są jasne.

Wyjaśnienie zadania

Przykładowe zadanie polega na wczytaniu liczby naturalnej określającej numer elementu ciągu Fibonacciego, obliczeniu tego elementu i jego wypisaniu.

Dane należy wczytywać ze standardowego wejścia (można założyć, że z klawiatury), a odpowiedź wypisać na standardowe wyjście (można założyć, że na ekran). Innymi słowy można użyć na przykład strumieni (std::cin oraz std::cout). Można też używać funkcji z biblioteki cstdio (scanf oraz printf), albo jeszcze innych: na~przykład gets/puts. Tak naprawdę, system sprawdzający na standardowe wejście podaje plik, a odpowiedź programu zapisywana jest do pliku, ale cały proces jest dla programu niezauważalny, więc zawodnik nie musi się tym przejmować.

Program powinien zatem oczekiwać na wczytanie jednej liczby i jeśli otrzyma na przykład 4, oznacza to, że powinien obliczyć czwartą liczbę Fibonacciego. Liczby Fibonacciego numer 0 i 1 to jedynki, a każda kolejna jest sumą dwóch poprzednich, więc na przykład druga liczba Fibonacciego to 1+1 = 2, trzecia to 2+1 = 3, a czwarta to 3+2 = 5. Program powinien więc dla danej 4 wprowadzonej z klawiatury (pytanie o czwartą liczbę Fibonacciego) wypisać na ekran wynik 5 (ile ona wynosi).

W sekcji Wejście napisano, że liczba będzie naturalna z zakresu od 0 do 80 włącznie. To znaczy, że program ma działać nie tylko dla danej 4, ale również 0, 1, 17, 35, 80 i wielu innych. Przykładowo, jeśli do programu wprowadzimy 0, powinien on wypisać 1, a jeśli wprowadzimy 80 powinien wypisać 37889062373143906. W każdym zadaniu olimpijskim można założyć, że dane będą zgodne ze specyfikacją. W przypadku tego zadania nikt zatem nie będzie wprowadzał do Twojego programu danej 1.5, ani alamakota, nie ma więc konieczności sprawdzania tego. Nie jest też ważne, jak zachowałby się program w takiej sytuacji.

Możliwe błędy

Przeanalizujemy najpierw kilka nieprawidłowych rozwiązań zadania.

Nieprawidłowy algorytm

Spróbujmy napisać pierwszy program:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;

  cin >> n;  // test przykładowy: 4

  cout << n + 1 << "\n";   // odpowiedź poprawna: 5

  return 0;
}

Program działa prawidłowo dla danych przykładowych z treści zadania, tzn. po wprowadzeniu do programu liczby 4 uzyskamy 5, czyli dokładnie tak jak powinno być.

Po wysłaniu zgłoszenia do SIO2, uzyskamy następujący raport z oceny rozwiązania: Jest to jedynie raport z oceny na testach przykładowych - w tym przypadku jedynie na teście 4 z treści zadania. Skoro program prawidłowo wypisuje dla tych danych wynik 5, otrzymuje status OK.

Nie oznacza to jednak, że zadanie zostało rozwiązane prawidłowo. Po kliknięciu przycisku Odsłoń wynik, naszym oczom ukazuje się: A zatem zgłoszenie zostało ocenione na 0 punktów.

Po zawodach, gdy wysyłanie zgłoszeń nie będzie już możliwe, zawodnik uzyskuje dostęp do pełnego raportu oceny rozwiązania: Dla większości testów został ustalony werdykt Błędna odpowiedź.

Uwaga: Na zawodach właściwych (tzn. wszystkich turach wszystkich etapów) zawodów OIJ tak szczegółowy raport udostępniany jest zawodnikom dopiero po zawodach. W trakcie zawodów widoczny jest jedynie wynik sprawdzenia na testach przykładowych, a wynik punktowy zgłoszenia nie jest jawny. Jedynie podczas tury “otwartej” pierwszego etapu możliwe jest odsłonięcie wyniku niektórych nadesłanych zgłoszeń (należy pamiętać, że wynik zgłoszeń na danym zadaniu można odsłonić tylko ustaloną liczbę razy, zgodnie z Zasadami organizacji zawodów). Odsłonięcie wyniku ujawnia jedynie liczbę punktów, a pełny, szczególowy raport z oceny nadal jest tajny, nawet podczas tury “otwartej” pierwszego etapu.

Program jest niepoprawny, bo nie jest prawdą, że N-ta liczba Fibonacciego jest zawsze równa N+1. Na przykład, dla danej 5, program wypisze 6, a powinien wypisać 8.

Zadaniem każdego zawodnika na Olimpiadzie jest zawsze sprawdzić działanie programu na różnych, również złośliwych danych testowych. Jurorzy dokładają wszelkich starań, żeby możliwie najpełniej testować poprawność i wydajność programów zawodników, można więc śmiało założyć, że w zbiorze danych testowych zawarto różne testy, także inne niż 4.

Można zapytać, dlaczego program uzyskał 0 punktów, chociaż nawet na SIO2 zaliczone zostały dwa testy: jeden przykładowy i jeden punktowany (program zadziałał poprawnie jeszcze dla N = 0)? Czy nie powinniśmy uzyskać chociaż kilku punktów, skoro program czasami działa, a czasami nie? Wszystkiemu winne jest grupowanie testów: każdej grupie testów (składającej się z jednego lub wielu różnych możliwych pojedynczych testów, czyli danych do programu) przypisana jest pewna liczba punktów. Jeśli ocenimy każdy test z osobna, wynik za całą grupę obliczany jest jako minimum z całej grupy testów: jeśli więc program nie zaliczy choćby jednego testu z danej grupy, otrzyma za nią 0 punktów. Testy z tej samej grupy mają ten sam numer, ale mają dopisaną literkę (np. testy 2a i 2b należą do tej samej grupy testów, a test 3 stanowi sam osobną grupę).

Każde zadanie na Olimpiadzie można spróbować rozwiązać wiele razy (limit podany jest w Zasadach organizacji zawodów). Podczas zawodów I stopnia wynikiem za zadanie uznaje się maksimum pośród wszystkich wyników z wysłanych zgłoszeń dla danego zadania.

Błąd kompilacji

Zmieniamy więc pomysł i implementujemy następujące rozwiązanie:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cin >> n;
  for (int i = 2; i <= n; i++) {
    long long fib_nast = fib_poprz + fib_akt   // zapomniany średnik
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Po wysłaniu rozwiązania do systemu SIO2 uzyskamy werdykt Błąd kompilacji. Rzeczywiście, takiego programu nie można uruchomić, bo się nie skompiluje z powodu zapomnianego średnika. Niestety, pomimo tego, że od rozwiązania poprawnego dzieli nas tylko jeden znak, nadal ten kod wart jest 0 punktów. Co więcej, skoro programu nie udało się skompilować, nie został nawet uruchomiony na testach. SIO2 wyświetla jedynie błąd kompilacji, który pomaga zidentyfikować i naprawić problem.

Wysłanie programu wykonywalnego zamiast kodu źródłowego

Powiedzmy, że naprawiliśmy program i umieśliliśmy go w pliku program.cpp, ale podczas wysyłki do SIO2, wyślemy plik wykonywalny program.exe. Wówczas SIO2 nie przyjmie takiego rozwiązania do oceny. Z kilku powodów:

• do oceny uwzględniane są kody źródłowe, a nie programy wykonywalne,
• program musi być napisany w jednym z dostępnych języków programowania i kompilować się z flagami podanymi w Zasadach organizacji zawodów i Ustaleniach technicznych,
• jest limit długości wysyłanego kodu (a bardzo możliwe, że program wykonywalny ten limit przekracza).

Dodatkowe komunikaty

No dobrze, postanawiamy w końcu wysłać właściwy program, ale zanim to nastąpi, przyszło nam do głowy “upiększyć” go o dodatkowe komunikaty pomagające zrozumieć co robi program i co należy do niego wprowadzić.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cout << "Podaj n: ";   // błąd: ładne komentarze spowodują błędną odpowiedź
  cin >> n;

  cout << "Obliczam...\n";
  for (int i = 2; i <= n; i++) {
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << "Wynik to: " << fib_akt << "\n";

  system("PAUSE");   // błąd: wywołanie system jest niedozwolone

  return 0;
}

Taki program wysłany na SIO2 otrzyma na wszystkich testach werdykt Błędna odpowiedź, Błąd wykonania lub Naruszenie bezpieczeństwa.

Po pierwsze: wywołanie funkcji system potencjalnie mogłoby uruchomić inny program, co mogłoby być niebezpieczne dla systemu sprawdzającego: np. system("rm -Rf /");.

Po drugie: program powinien wypisywać informacje dokładnie w takim formacie jak podano w sekcji Wyjście. System sprawdzający nie jest człowiekiem, nie rozumie ludzkich komunikatów i jedynie stwierdza, że zamiast wypisać odpowiedź 5 dla testu przykładowego, program wypisuje Podaj n: i serię dodatkowych komunikatów. Należy zawsze pamiętać, żeby dane były wypisane w formacie zgodnym z sekcją Wyjście.

Zły typ danych

Dobrze, wycofujemy się z pomysłu upiększania programu i wysyłamy na SIO2 następujący program:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, fib_poprz = 1, fib_akt = 1;  // błąd: 80-ta liczba Fibonacciego jest za duża na typ int

  cin >> n;
  for (int i = 2; i <= n; i++) {
    int fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Program ten w końcu otrzymuje punkty! Ale niestety, nie uzyskuje maksimum. Zmienna typu int pozwala przechowywać jedynie liczby całkowite z określonego zakresu (od około minus dwóch miliardów do około plus dwóch miliardów). 80-ta liczba Fibonacciego znacznie przekracza dwa miliardy. Po przekroczeniu zakresu działanie programu jest nieokreślone (zwykle zmienna osiąga ujemne wartości).

Błąd można wykryć samemu: wystarczy wprowadzić do programu daną 46. Najprawdopodobniej uzyskamy -1323752223, co z pewnością nie jest poprawną odpowiedzią. Aby to naprawić, należy skorzystać z typu danych, który pozwala przechowywać liczby większe, na przykład long long. Zakres zmiennej tego typu również jest ograniczony, jednak jest większy (zmienne long long zwykle pozwalają przechowywać liczby do 18 cyfr włącznie).

Program uzyskał 70 punktów, dlatego że jeśli N podane na wejściu nie przekracza 45, program działa prawidłowo. W treści zadania zaś w sekcji Ocenianie napisane było, że testy warte 70% punktów mają N właśnie do 45. W zadaniach trudniejszych, często możliwe jest na przykład wymyślenie algorytmu poprawnego, ale działającego zbyt wolno na dużych danych. Z sekcji Ocenianie często możliwe jest wywnioskowanie ile punktów otrzyma takie rozwiązanie. Zazwyczaj poprawne, ale za wolne rozwiązania otrzymują pewną, dodatnią liczbę punktów. Intencją Jury jest natomiast, żeby rozwiązania algorytmicznie błędne otrzymywały bardzo mało punktów (często nawet 0).

Za dużo zużytej pamięci

Przyszedł nam do głowy dowcip. Do poprawnego rozwiązania, dla hecy dodajemy ogromną tablicę miliarda zmiennych typu int:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  int tabliczka[1000000000];  // haha, tablica dla szpanu!

  cin >> n;
  for (int i = 2; i <= n; i++) {
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Taki program wysłany na SIO2 otrzyma 0 punktów i werdykt Błąd wykonania lub Przekroczenie limitu pamięci. W każdym zadaniu olimpijskim podany jest limit pamięci. Jeśli program przekroczy ów limit, jego wykonanie na systemie sprawdzającym jest przerywane. Nie zawsze jest oczywiste, czy program został przerwany z powodu przekroczenia limitu pamięci czy z powodu innego błędu (na przykład naruszenia bezpieczeństwa, złego dostępu do pamięci czy dzielenia przez zero), dlatego czasami przekroczenie limitu pamięci może być sygnalizowane również jako Błąd wykonania. Niezależnie od kwalifikacji błędu, program, który nie uzyskuje statusu OK otrzymuje 0 punktów za dany test. Ponieważ tablica jest tworzona niezależnie od danych wejściowych, program przekracza pamięć na każdym teście, więc nie zdobywa żadnych punktów.

Może się również zdarzyć, że program otrzyma status Błąd kompilacji (kompilator na etapie kompilacji może zaraportować błąd, że tablica jest zbyt duża).

Tablica stworzona w programie zajmowałaby 4 GB pamięci (jeden int zajmuje zwykle 4 bajty pamięci, tworzonych było miliard takich zmiennych).

W tym przypadku tworzona tablica nie miała żadnego sensu. Czasami jednak, gdy nasz pomysł zużywa zbyt wiele pamięci w najgorszym przypadku, dobrze jest zrobić mniejszą tablicę, być może za małą dla niektórych danych, ale tak, aby program był w stanie chociaż dla małych danych zadziałać poprawnie i mieszcząc się w limitach. W ten sposób ma szansę uzyskać częściowe punkty za działanie programu dla mniejszych danych zgodnie z sekcją Ocenianie z treści zadania.

Niedeterministyczny program

A gdyby napisać taki (prawie poprawny) program?

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cin >> n;
  for (int i; i <= n-2; i++) {  // początkowa wartość zmiennej i jest nieustalona
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Trudno przewidzieć jaki wynik zwróci program. Jeśli wartość zmiennej i po utworzeniu będzie równa 0, program zadziała prawidłowo. Jeśli jednak będzie inaczej pętla może wykonać się zbyt wiele razy lub zbyt mało razy, prowadząc do uzyskania werdyktu Błędna odpowiedź lub Limit czasu przekroczony. Działanie programu jest nieustalone, bowiem standard języka C++ nie precyzuje jaką wartość przyjmie niezainicjalizowana zmienna. Może się okazać, że na Twoim komputerze program będzie działał prawidłowo (bo akurat tak się złoży, że zmienna otrzyma prawidłową wartość), a na SIO2 nie (bo zmienna uzyska tam inną wartość początkową). Wiążący dla końcowego wyniku zawodnika jest oczywiście wynik oceny na SIO2. Należy pisać programy w taki sposób, żeby działały poprawnie zawsze, niezależnie od tego, na jakim komputerze zostaną uruchomione. W przeciwnym razie zawodnik naraża się na niebezpieczeństwo uzyskania niskiej punktacji (czasami, lub wręcz często) 0 punktów.

Powyższy przykład pokazuje również, że u mnie działa nie jest argumentem, że program jest poprawny. Dobrze napisany program działa zawsze, a źle napisany być może działa czasami. Na Olimpiadzie wysoką punktację uzyskują programy poprawne i szybkie.

Uruchomienie próbne

Z pomocą na przypadki podobne do tego wyżej przychodzi funkcja Uruchomienie próbne. Pozwala ona uruchomić program w środowisku SIO2 dla własnych danych i przejrzenie wyniku jaki zwróci program oraz sprawdzenie jego czasu wykonania (zgodnie z narzędziem ojejq).

Uruchomienie próbne NIE jest tym samym co wysłanie zgłoszenia:

• dla uruchomień próbnych jest zupełnie osobny limit programów, które można nadesłać niż limit zgłoszeń,
• program uruchamiany jest na dokładnie takich danych jak wysłane przez zawodnika, a nie na danych przygotowanych przez organizatorów,
• możliwe jest pobranie odpowiedzi, którą zwrócił program na wyjście,
• NIE jest sprawdzana ani poprawność nadesłanych danych wejściowych do programu, ani NIE jest sprawdzana poprawność odpowiedzi programu dla tych danych,
• sprawdzane jest natomiast czy program się kompiluje, czy zmieścił się w limicie czasu, limicie pamięci, czy nie nastąpił błąd wykonania podczas działania, czy nie nastąpiło naruszenie reguł uruchomienia.

Celem uruchomienia próbnego jest umożliwić zawodnikowi sprawdzenie czy program działa w warunkach SIO2 tak samo jak na maszynie zawodnika. Jeśli zawodnik zna prawidłową odpowiedź dla nadesłanych przez siebie danych, może porównać czy program zadziałał zgodnie z oczekiwaniami. Funkcja jest również szczególnie przydatna, gdy zawodnik martwi się o limit zgłoszeń, gdyż nadesłane uruchomienia próbne nie są wliczane do tego limitu. Należy jednak pamiętać, aby nie pomylić tej funkcji z właściwym wysłaniem rozwiązania do oceny. Aby zgłoszenie było brane pod uwagę przy obliczaniu wyniku zawodnika, należy je zgłosić używając opcji Wyślij w SIO2.

Drobny błąd w przypadku brzegowym

Poprawiamy program i nieco go zmieniamy:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cin >> n;
  int i = 1;
  do {
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;   // błąd! wykona się zawsze, nawet gdy n jest 0 lub 1
    i++;
  } while (i < n);

  cout << fib_akt << "\n";

  return 0;
}

Program nie zalicza jedynie dwóch testów: tych, w których N jest równe 0 lub N jest równe 1. Spowodowane jest to błędem implementacyjnym. Pętla wykona się zawsze co najmniej raz, a zatem zwrócony wynik jest co najmniej 2. Należy pamiętać o testowaniu programu na różnych danych: również tych minimalnego rozmiaru.

Rozwiązanie rekurencyjne: zbyt wolne

Zanim poprawiliśmy błąd, wpadł nam do głowy pomysł użycia rekurencji: skoro liczby Fibonacciego zdefiniowane są rekurencyjnie, może warto napisać program bezpośrednio z definicji?

#include <bits/stdc++.h>
using namespace std;

long long fib(int n) {
  if (n == 0)
    return 1;
  if (n == 1)
    return 1;
  return fib(n-1) + fib(n-2);  // będzie wolne
}

int main() {
  int n;

  cin >> n;
  cout << fib(n) << "\n";

  return 0;
}

Program otrzymuje jedynie 50 punktów i na niektórych testach uzyskuje werdykt Limit czasu przekroczony. Oznacza to, że jest zbyt wolny (lub się zapętla).

Rzeczywiście, program uruchomiony dla danej 10 zwraca wynik bardzo szybko, jednak już na przykład dla danej 40 obliczenie wyniku trwa kilka sekund, a dla danych większych może to trwać kilka godzin, dni lub jeszcze dłużej.

Limit czasu w większości zadań olimpijskich waha się w przedziale od pół sekundy do kilku(nastu) sekund. W tym zadaniu limit wynosi pół sekundy, chociaż nawet jeśli byłby nieco większy, program i tak nie miałby żadnych szans na ukończenie działania dla wejścia 80.

Powodem wolnego działania programu jest fakt, że funkcja fib obliczana jest wielokrotnie dla tych samych parametrów. W szczególności, ponieważ program zwraca prawidłowy wynik, dla dowolnej danej N, program uruchamia funkcję fib z parametrem 0 lub 1 dokładnie tyle razy, ile wynosi N-ta liczba Fibonacciego. W końcu prawidłowy wynik ostatecznie bierze się z posumowania jedynek na końcu drzewa rekursji. A ponieważ zauważyliśmy już wcześniej, że wynik może być bardzo duży, wiemy dlaczego powyższy program jest bardzo wolny.

Program radzi sobie dobrze dla danych, w których wynik jest nieduży (rzędu kilku milionów). Dla N nie przekraczających 30, czas wykonania jest jeszcze niezauważalny. Dlatego, zgodnie z sekcją Ocenianie, program uzyskał połowę maksymalnej liczby punktów.

Rozwiązanie poprawne

Zapominamy o powyższym rozwiązaniu i w końcu wysyłamy do systemu poprawiony kod źródłowy jednej z pierwszych wersji programu:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cin >> n;
  for (int i = 2; i <= n; i++) {
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

i otrzymujemy upragnione 100 punktów.

Uwaga! Jedynie podczas tury “otwartej” pierwszego etapu OIJ zawodnicy mogą odsłonić pełny wynik niektórych swoich zgłoszeń. W turze “ukrytej” pierwszego etapu oraz w drugim i trzecim etapie zawodów, zawodnik po nadesłaniu widzi jedynie wynik testów przykładowych podanych w treści zadania (oraz być może kilku dodatkowych testów) wartych 0 punktów.

Pełny wynik oceny zgłoszenia będzie znany dopiero po zawodach, gdy nie będzie już możliwości zmieniania programu. Dlatego tak ważne jest testowanie programu samodzielnie na różnych (również bardzo złośliwych) danych. Inaczej może się okazać, jak w przypadku niektórych wcześniej pokazanych programów, że SIO2 pokaże werdykt OK na testach przykładowych, ale właściwy wynik na punktowanych testach niejawnych będzie mizerny.

Inne rozwiązanie poprawne: z użyciem tablicy

A co jeśli przyszłoby nam do głowy jednak użyć tablicy?

// również poprawne rozwiązanie z tablicą (nie za dużą)

#include <bits/stdc++.h>
using namespace std;

long long fib[90];

int main() {
  int n;

  cin >> n;

  fib[0] = 1;
  fib[1] = 1;
  for (int i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];

  cout << fib[n] << "\n";

  return 0;
}

Okazuje się, że takie rozwiązanie również zostanie zaakceptowane pomimo nieco większego zużycia pamięci niż rozwiązanie poprzednie. Tak długo jak program mieści się w limitach podanych w treści zadania na wszystkich danych, tak długo otrzymuje maksymalną punktację. Nie jest zatem potrzebne przesadne optymalizowanie programu. Zwykle kluczem do zaakceptowania zadania nie jest przeoptymalizowana implementacja, lecz poprawny algorytm, bez błędów implementacyjnych, który ma optymalną (lub bliską optymalnej) złożoność obliczeniową i pamięciową. Więcej na ten temat można przeczytać na przykład tutaj.

Inne rozwiązanie poprawne: bardzo skrócony kod

Z tych samych powodów poniższy program:

// krótki i brzydki, ale poprawny kod
#include <iostream>
typedef long long L;int main(){int n;L f,g,h;f=g=1;std::cin>>n;for(int i=1;i<n;i++){h=f+g;f=g;g=h;}std::cout<<g<<"\n";return 0;}

również uzyska 100 punktów, ani mniej, ani więcej. Miarą oceny programu na olimpiadzie jest poprawność, szybkość działania i zużycie pamięci, a nie długość kodu źródłowego. A zatem nie ma żadnego bonusa za krótsze kody programów. Nie jest też prawdą, że program krótszy jest zawsze szybszy niż dłuższy, więc przesadne skracanie kodu mija się z celem. Jedyne, o czym należy pamiętać to limit długości kodu źródłowego, ale ten jest na tyle długi, że w praktyce niemożliwym jest jego przekroczenie. Wyjątkiem byłaby sytuacja, gdy kod programu miałby być generowany automatycznie, zamiast być pisany ręcznie.

Przykład powyżej również pokazuje, że ocenie nie podlega styl implementacji i przestrzeganie dobrych reguł pisania kodu. Automatyczny system sprawdzający ignoruje treść kodu, od razu przechodząc do jego kompilacji i uruchomienia na zbiorze wcześniej przygotowanych danych. Mimo to jednak, polecamy pisać programy rozsądnie. Z reguły programy napisane brzydko, z rażącym naruszeniem dobrych praktyk, są również niepoprawne lub wolne.

Inne rozwiązanie poprawne: rozwiązanie rekurencyjne ze spamiętywaniem

Możliwe jest również poprawienie rozwiązania rekurencyjnego, które wcześniej było za wolne, poprzez dodanie spamiętywania:

#include <bits/stdc++.h>
using namespace std;

long long obliczone[90];  // jeśli 0 to znaczy, że jeszcze nieobliczone

long long fib(int n) {
  if (n == 0)
    return 1;
  if (n == 1)
    return 1;
  if (obliczone[n] == 0)   // obliczamy tylko jeśli wcześniej nie obliczyliśmy
    obliczone[n] = fib(n-1) + fib(n-2);   // spamiętaj wynik w tablicy
  return obliczone[n];
}

int main() {
  int n;

  cin >> n;
  cout << fib(n) << "\n";

  return 0;
}

Funkcja fib najpierw sprawdza czy nie została wcześniej uruchomiona dla tej danej. Jeśli tak, korzysta z wcześniej obliczonego i zapamiętanego wyniku. Dzięki temu, każdy wynik obliczany jest jedynie raz, za pierwszym razem gdy jest potrzebny. Program działa tylko nieznacznie wolniej od poprzednich i również uzyskuje maksymalną punktację.

Inne rozwiązanie poprawne: rozwiązanie z arytmetyką dużych liczb

Typ long long choć ma zakres większy niż int, również ma swoje ograniczenia. Na przykład, próbując wprowadzić do programu 92, również prawdopodobnie uzyskamy nieprawidłowy, ujemny wynik. Istnieje możliwość obejścia tych ograniczeń poprzez implementację własnej arytmetyki dużych liczb - algorytmu dodawania pisemnego:

#include <bits/stdc++.h>
using namespace std;

string Dodaj(string a, string b) {
  // funkcja dodaje dwie liczby zapisane w systemie dziesiątkowym jako napisy
  // i zwraca wynik jako napis

  reverse(a.begin(), a.end());  // odwróć cyfry liczb
  reverse(b.begin(), b.end());

  while (a.length() < b.length())
    a.push_back('0');   // dopełnij zerami
  a.push_back('0');  // dodaj jedno zero (na ewentualne przepełnienie)
  b.push_back('0');

  for (int i = 0; i < a.length()-1; i++) {
    a[i] += b[i] - '0';
    if (a[i] > '9') {
      a[i + 1]++;
      a[i] -= 10;
    }
  }

  if (a.back() == '0')  // jeśli nie było przepełnienia, pozbądź się zera
    a.pop_back();

  reverse(a.begin(), a.end());  // odwróć zapis do normalnej kolejności cyfr

  return a;
}

int main() {
  int n;
  string fib_poprz("1"), fib_akt("1");

  cin >> n;
  for (int i = 2; i <= n; i++) {
    string fib_nast = Dodaj(fib_poprz, fib_akt);
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Rozwiązanie również uzyskuje maksymalną punktację i działa nawet dla danych znacznie przekraczających ograniczenia podane w treści zadania. Limity są jednak zwykle dobierane, aby ta sztuczka nie była konieczna (choć nie jest to regułą). Tak było i w przypadku tego zadania.

Inne rozwiązanie poprawne: szybkie potęgowanie macierzy

Ten fragment radzimy traktować jako dodatkowy, jedynie dla zainteresowanych Czytelników.

Z użyciem zaawansowanych metod algebry liniowej, możliwe jest rozwiązanie zadania istotnie szybciej:

// zaawansowane rozwiązanie z potęgowaniem macierzy

#include <bits/stdc++.h>
using namespace std;

struct Macierz22 {
  long long a, b, c, d;

  Macierz22(long long a, long long b, long long c, long long d):
    a(a), b(b), c(c), d(d) {}

  Macierz22 operator*(const Macierz22& r) const {
    long long ra = a * r.a + b * r.c;
    long long rb = a * r.b + b * r.d;
    long long rc = c * r.a + d * r.c;
    long long rd = c * r.b + d * r.d;
    return Macierz22(ra, rb, rc, rd);
  }

  Macierz22 potega(int n) {  // działa w czasie O(log n)
    if (n == 0)
      return Macierz22(1, 0, 0, 1);

    Macierz22 h = potega(n / 2);

    if (n % 2 == 0)
      return h * h;
    return (*this) * h * h;
  }
};

int main() {
  int n;

  cin >> n;

  // potęgujemy macierz
  // (1 1)
  // (1 0)
  // do potęgi n
  Macierz22 w = Macierz22(1, 1, 1, 0).potega(n);

  // i odczytujemy lewy górny róg macierzy
  cout << w.a << "\n";

  return 0;
}

Rozwiązanie jest istotnie lepsze, bo wykonuje jedynie O(log N) iteracji, zamiast O(N) we wszystkich wcześniejszych zaakceptowanych rozwiązaniach. W naszym zadaniu implementacja takiego rozwiązania nie ma żadnego sensu, bo zanim rozwiązanie pokaże swoją wyższość nad innymi, N będzie musiało być ogromne, a zyski z implementacji szybszego rozwiązania, skonsumowane będą przez konieczność implementacji bardziej złożonych operacji na dużych liczbach (między innymi mnożenia).

Czasami jednak takie rozwiązanie miałoby sens - na przykład, gdyby zapytać o ostatnich dziewięć cyfr N-tej liczby Fibonacciego w zapisie dziesiętnym. Każde obliczenie można wtedy wykonać modulo miliard (w C++ używamy do tego operatora %), co pozwala uniknąć konieczności implementowania arytmetyki dużych liczb. Wtedy program można uruchomić dla N nawet rzędu tryliona, a program błyskawicznie obliczy odpowiedź, podczas gdy pozostałe programy nie zakończyłyby pracy w ciągu kilku dni.

Więcej informacji o tym sposobie rozwiązania można uzyskać tutaj. Warto podkreślić, że ta tematyka znacznie wykracza poza program OIJ. Stosowanie jej nie jest zakazane, jednak organizatorzy dobierając zadania będą starali się, aby stosowanie tej sztuczki nie było konieczne.

Inne rozwiązanie poprawne: spamiętane liczby Fibonacciego w kodzie programu

Do rozwiązania można podejść jeszcze inaczej. Skoro N jest liczbą naturalną między 0 a 80, to istnieje zaledwie 81 możliwych przypadków do rozpatrzenia. Ciąg Fibonacciego jest bardzo znany, więc znalezienie go w encyklopedii ciągów liczbowych nie jest zbyt trudne. Równie łatwe jest odszukanie tabeli pierwszych dwóch tysięcy elementów ciągu Fibonacciego. Możliwe jest więc napisanie następującego programu:

#include <bits/stdc++.h>
using namespace std;

// ciąg znaleziony na https://oeis.org/A000045/b000045.txt
const long long WYNIKI[] = {
  1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,
  17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,
  3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,
  165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,
  4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,
  86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
  1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,
  17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,
  190392490709135,308061521170129,498454011879264,806515533049393,
  1304969544928657,2111485077978050,3416454622906707,5527939700884757,
  8944394323791464,14472334024676221,23416728348467685,37889062373143906 };

int main() {
  int n;
  cin >> n;
  cout << WYNIKI[n] << "\n";

  return 0;
}

Program ma zapisane wyniki dla wszystkich możliwych testów, jakie są dozwolone w zadaniu (patrz sekcja Wejście). Tak długo, jak długość kodu nie przekracza limitu długości kodu podanego w Zasadach Organizacji Zawodów, tak długo jest to rozwiązanie dopuszczalne.

Umieszczenie komentarza, skąd pochodzi ciąg jest wskazane. Wyobraźmy sobie, że więcej niż jeden zawodnik wpadł na ten pomysł. Organizatorzy weryfikują na różne sposoby, czy rozwiązania zawodników są samodzielne. Jeśli dwa kody są podobne, może (choć nie musi) to oznaczać, że zawodnicy współpracowali. Dlatego, zgodnie z Regulaminem zawodów, użycie kawałków programów dostępnych w internecie, książkach lub innych publicznych źródłach jest dozwolone, pod warunkiem podania źródła. Należy pamiętać jednocześnie, że niesamodzielna praca, a w szczególności (choć nie tylko) wymienianie się programami, może skutkować dyskwalifikacją zaangażowanych zawodników.

O ocenie rozwiązań

Zainteresowany Czytelnik zauważył być może pewien problem ze zaproponowanym sposobem automatycznej oceny rozwiązań. Czy poniższy program jest poprawny?

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  long long fib_poprz = 1, fib_akt = 1;

  cin >> n;

  if (n == 67) {
    // dla zabawy, ciekawe czy testy to wykryją...
    cout << "HAHAHA!\n";
    return 0;
  }

  for (int i = 2; i <= n; i++) {
    long long fib_nast = fib_poprz + fib_akt;
    fib_poprz = fib_akt;
    fib_akt = fib_nast;
  }

  cout << fib_akt << "\n";

  return 0;
}

Rzecz jasna, jeśli wprowadzić do programu 67, program wypisze na wyjście napis HAHAHA! zamiast 67-tej liczby Fibonacciego, co oczywiście nie jest poprawnym wynikiem. Jeśli jednak 67 nie zostało umieszczone w zbiorze danych testowych, błąd nie zostanie wykryty. Oznacza to, że jest możliwe, że takie rozwiązanie uzyska 100 punktów i werdykt OK na wszystkich testach. Mimo wszelkich starań, pokrycie testami wszystkich możliwych przypadków jest często niewykonalne (zbyt duża liczba przypadków do sprawdzenia). Smutnym faktem jest również to, że ułomność tego systemu oceny nie wynika z ograniczeń organizatorów, lecz ograniczeń samej informatyki.

System sprawdzający dba o to, żeby odpowiedź wypisana przez program zawodnika była prawidłowa. Tak długo, jak program zawodnika wypisuje prawidłową odpowiedź mieszcząc się w ustalonych limitach, otrzymuje maksymalny wynik - również jeżeli program nie wczytywałby wejścia lub odpowiedź była wylosowana albo zapisana na stałe do kodu programu.