Wersja dla języka Python

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 funkcji input(), metody read() albo readlines() obiektu sys.stdin. Można też iterować po kolejnych liniach obiektu sys.stdin. 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:

n = int(input())
print(n+1)

Uwaga: System SIO2 używa Pythona 3, zwróć uwagę, że niektóre konstrukcje znane z Pythona 2 (np. print bez nawiasów) nie działają.

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 składni

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

fib_poprz, fib_akt = 1, 1
n = int(input())
for i in range(2, n+1)    # zapomniany dwukropek
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast

print(fib_akt)

Po wysłaniu rozwiązania do systemu SIO2 uzyskamy werdykt Błąd kompilacji. Co prawda język Python jest językiem interpretowalnym, jednak zanim SIO2 spróbuje uruchomić program w tym języku, sprawdzana jest poprawność składni programu. Jeśli podczas tego sprawdzenia wystąpi błąd, raportowany jest werdykt Błąd kompilacji.

Rzeczywiście, takiego programu nie można uruchomić, bo jest niepoprawny składniowo z powodu zapomnianego dwukropka. 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 program jest niepoprawny składniowo, nie został nawet uruchomiony na testach. SIO2 wyświetla jedynie błąd kompilacji, który pomaga zidentyfikować i naprawić problem.

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

fib_poprz, fib_akt = 1, 1
n = int(input('Podaj n: '))
print('Obliczam...')
for i in range(2, n+1):
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast

print('Wynik to: {}'.format(fib_akt))

Taki program wysłany na SIO2 otrzyma na wszystkich testach werdykt Błędna odpowiedź.

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.

Za dużo zużytej pamięci

Przyszedł nam do głowy dowcip. Do poprawnego rozwiązania, dla hecy dodajemy ogromną listę rozmiaru miliard wypełnioną liczbami 0:

tabliczka = [0] * 1000000000   # haha, tablica dla szpanu!

fib_poprz, fib_akt = 1, 1
n = int(input())
for i in range(2, n+1):
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast

print(fib_akt)

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.

Lista stworzona w programie zajmowałaby co najmniej 4 GB pamięci.

W tym przypadku tworzona lista nie miała żadnego sensu. Czasami jednak, gdy nasz pomysł zużywa zbyt wiele pamięci w najgorszym przypadku, dobrze jest zrobić mniejszą listę, 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.

Drobny błąd w przypadku brzegowym

Poprawiamy program i nieco go zmieniamy:

fib_poprz, fib_akt = 1, 1
n = int(input())
i = 1
while True:
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast
  i += 1
  if i >= n: break

print(fib_akt)

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?

def fib(n):
  if n == 0:
    return 1
  if n == 1:
    return 1
  return fib(n-1) + fib(n-2)

n = int(input())
print(fib(n))

Program otrzymuje jedynie 30 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 35 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 20, czas wykonania jest jeszcze niezauważalny.

Zgodnie z sekcją Ocenianie, intencją autora zadania było, aby program uzyskał połowę maksymalnej liczby punktów. Tak się jednak nie stało. Analogiczny program w języku C++ dla danej 30 działa w czasie 0.01-0.02 sekundy (jedna lub dwie setne sekundy) według pomiaru narzędziem ojejq (więcej o tym narzędziu można dowiedzieć się tutaj), jednak jego wersja w Pythonie przekracza 0.5 sekundy dla tych samych danych, czyli jest co najmniej 25 razy wolniejsza! Niestety, wynika to z różnic na poziomie języka programowania i bardzo często sensownie napisany program w C++ jest wielokrotnie szybszy od analogicznej wersji w Pythonie. Wybór języka programowania jest częścią rozwiązania zadania. Dla przykładu: gdyby N w tym zadaniu mogło być większe, na~przykład równe 1000, program w Pythonie dalej zwracałby poprawną odpowiedź, a program w C++ musiałby być radykalnie zmieniony: konieczna byłaby implementacja własnej arytmetyki dużych liczb, która w Pythonie jest domyślnie gotowa do użycia. W rozwiązaniu tego zadania w języku C++ jest też kilka dodatkowych miejsc, gdzie można łatwo przez przypadek popełnić błąd i stracić punkty. Jak widać, implementowanie rozwiązania olimpijskiego w Pythonie ma swoje wady i zalety. Znajomość wielu języków programowania pozwala wybrać najwłaściwsze narzędzie do rozwiązania zadania.

Organizatorzy dokładają wszelkich starań, żeby zadania można było zaakceptować we wszystkich dopuszczonych językach programowania. Niestety, z powodu bardzo dużych różnic czasowych rozwiązań w Pythonie i C++, nie zawsze możliwe jest dobranie limitów w taki sposób, żeby odróżnić rozwiązanie w Pythonie o lepszej złożoności obliczeniowej od rozwiązania w C++ o gorszej złożoności obliczeniowej. Programując w Pythonie trzeba być więc szczególnie wyczulonym na optymalność implementacji rozwiązania. Kilka uwag n.t. pisania kodu, w taki sposób, żeby był wydajny znajduje się w dokumentacji.

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). Na przykład: możliwe byłoby sprawdzenie w jakim czasie wykona się program z poprzedniej sekcji, jeśli wprowadzimy do niego daną 30.

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.

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:

fib_poprz, fib_akt = 1, 1
n = int(input())
for i in range(2, n+1):
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast

print(fib_akt)

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?

n = int(input())

fib = [1, 1]
for i in range(2, n+1):
  fib.append(fib[-1] + fib[-2])
print(fib[n])

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
fp,fa=1,1;n=int(input());
for i in range(2,n+1):
  fn=fp+fa;fp=fa;fa=fn
print(fa)

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:

obliczone = {}

def fib(n):
  global obliczone
  if n == 0:
    return 1
  if n == 1:
    return 1
  if n in obliczone:
    return obliczone[n]
  obliczone[n] = fib(n-1) + fib(n-2)
  return obliczone[n]

n = int(input())
print(fib(n))

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: 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

class Macierz22:
  def __init__(self, a, b, c, d):
    self.a, self.b, self.c, self.d = a, b, c, d

  def pomnoz(self, r):
    ra = self.a * r.a + self.b * r.c
    rb = self.a * r.b + self.b * r.d
    rc = self.c * r.a + self.d * r.c
    rd = self.c * r.b + self.d * r.d
    return Macierz22(ra, rb, rc, rd)

  def potega(self, n):   # działa w czasie O(log n)
    if n == 0:
      return Macierz22(1, 0, 0, 1)

    h = self.potega(n // 2)

    if n % 2 == 0:
      return h.pomnoz(h)
    return self.pomnoz(h).pomnoz(h)

n = int(input())
# potęgujemy macierz
# (1 1)
# (1 0)
# do potęgi n
w = Macierz22(1, 1, 1, 0).potega(n)

# i odczytujemy lewy górny róg macierzy
print(w.a)

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, należy również pamiętać, że dodawanie i mnożenie dużych liczb nie jest bez wpływu na wydajność.

Czasami jednak takie rozwiązanie miałoby większy 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 Pythonie 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:

FIB = [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]

n = int(input())
print(FIB[n])

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?

import sys

fib_poprz, fib_akt = 1, 1
n = int(input())

if n == 67:
  # dla zabawy, ciekawe czy testy to wykryją...
  print('HAHAHA!')
  sys.exit(0)

for i in range(2, n+1):
  fib_nast = fib_poprz + fib_akt
  fib_poprz = fib_akt
  fib_akt = fib_nast

print(fib_akt)

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.