Whoops

Po kolejnych poprawkach:

var
  d,n,i : longint;
  f : array[0..20000] of longint;

begin
  readln(d);
  while (d>0) do
  begin
    d:=d-1;
    readln(n);
    f[0]:=0; f[1]:=1;
    for i:=2 to n do f[i]:=f[i-1]+f[i-2];
    writeln(f[n] mod 10000);
  end;
end.

Wysłanie takiego programu spowoduje, że Sprawdzarka zwróci ocenę:

Wrong Answer

Oznacza to, że program wykonał się prawidłowo i nie przekroczył dopuszczalnego czasu, ale dał złą odpowiedź. W tym przypadku wkradł się nam błąd w implementacji (poprawnego) algorytmu. Z pozoru wygląda wszystko dobrze, ale liczby Fibonacciego są bardzo duże i ich reprezentacja nie zmieści się w typie longint, przez co "przekręca się licznik" i powstają bzdurne wartości (powinniście dowiedzieć się jakie ograniczenia mają poszczególne typy). Jeżeli nie chcecie pisać własnej obsługi dużych liczb (a pewnie nie chcecie), to wystarczy, że będziecie w tablicy f trzymać liczby Fibonacciego modulo 10000, zamiast pełne liczby i wykonywać operację modulo na samym końcu.

Ten konkretny błąd da się wykryć testując program na swoim stanowisku na danych z treści zadania. Często jednak będzie tak, że na danych z treści (które zazwyczaj są dość proste) Wasz program będzie działał poprawnie, a na testach na Sprawdzarce będzie dawał błędne wyniki. Zalecamy abyście przed wysłaniem rozwiązania do oceny przeprowadzili kilka własnych testów (choć i to nie zawsze pomaga). W razie znalezienia danych wejściowych, na których program działa źle, przydatnym narzędziem do wykrycia miejsca błędu może się okazać debugger, ale zalecamy też przemyślenie kodu programu. Możecie też wysłać program do wydrukowania, tak aby szukając błędów w swoim programie nie blokować komputera pozostałym członkom drużyny.

Uwaga! Wasz program może działać nieprawidłowo nie tylko dlatego, że popełniliście błąd w implementacji, ale także dlatego, że sam algorytm jest zły. Zamiast szukać błędu w kodzie, zastanówcie się, czy aby na pewno Wasz pomysł na rozwiązanie jest poprawny. Zastanówcie się też czy Wasz program będzie prawidłowo działał dla wszystkich możliwych przypadków szczególnych (np. najmniejszych możliwych liczb). Właśnie fakt, iż program myli się dla pewnych złośliwych/szczególnych danych jest jedną z częstszych przyczyn oceny Wrong Answer.

Dalej

Wstecz