-
Notifications
You must be signed in to change notification settings - Fork 81
[PL] 6. Paczka z weryfikacją wyjścia
Istnieje grupa zagadnień, które posiadają wiele poprawnych rozwiązań. Na razie omówione przez ten poradnik metody nie pozwalają na dobre radzenie sobie z takimi sytuacjami. Przykład: Wypisz na standardowe wyjście co najwyżej 10 liczb, których suma wynosi n. Nie da się zweryfikować odpowiedzi przez porównanie z odpowiedzią wzorcową dlatego, że istnieje wiele poprawnych podejść do podanego problemu. Można wypisywać po prostu liczbę n, można wypisać n - 1 i 1 itd. Nawet narzucając dodatkowe ograniczenia takie jak posortowane liczby na wyjściu, trudno poradzić sobie z takimi zadaniami. Z pomocą przyjdzie nam program weryfikujący, który możemy napisać i dołączyć do paczki.
Przygotujemy paczkę do zadania Puzzle, o skrócie puz. W zadaniu na wejściu podana będzie jedna liczba naturalna n oznaczająca długość boku prostokąta. Omawiany prostokąt będzie wymiarów 3 x n i będziemy chcieli pokryć go w całości małymi prostokątami wielkości 1 x 2, ustawiając je pionowo lub poziomo. Małe prostokąty nie mogą nachodzić na siebie, ani wychodzić poza duży prostokąt. Jeśli pola nie da się pokryć, powinniśmy wypisać zdanie Can't do that.
Jeśli liczba n nie jest podzielna przez 2, to zadania nie da się rozwiązać. Jest to spowodowane różną parzystością pola prostokąta i pojedynczej kostki (puzzla). W takim razie wypiszemy wtedy frazę Can't do that. Jeśli n jest liczbą parzystą, na pewno możemy pokryć pole, używając dokładnie 3n / 2 kostek. Jednym z najprostszych pokryć jest zakrycie całego prostokąta kładąc obok siebie poziomo kostki, idąc od lewej do prawej strony. Widać jednak, że nie jest to jedyne możliwe pokrycie.
Aby poradzić sobie z tym problemem napiszemy program puzchk.cpp. Za jego pomocą powiemy systemowi, które odpowiedzi powinien traktować za poprawne, a które za błędne, oraz ile punktów przyznać.
Przetwarzanie wejścia bywa bardzo uciążliwe. Jeśli chcemy dobrze zweryfikować plik, nie powinniśmy korzystać ze standardowych metod wczytywania (scanf, cin, input). W celu ułatwienia pracy (nie zapominając o bezpieczeństwie) powstała biblioteka oi.h. Posiada ona wiele funkcji do wczytywania wejścia. Można oczywiście zastosować dowolnie inną metodę, trzeba jednak pamiętać o tym, że uczestnicy mogą próbować różnych metod oszukania naszego programu sprawdzającego! W dalszej części poradnika będziemy korzystać z biblioteki oi.h, a program weryfikujący puzchk.cpp napiszemy w C++. Najpierw jednak, musimy omówić inne narzędzia, ułatwiające pracę nad paczką.
Wygodnym narzędziem do lokalnej pracy nad paczką jest program make. Działa on pod Linuxem, którego polecamy do pracy nad paczkami trudniejszymi niż te w pierwszych dwóch poradnikach. Make to program powłoki systemowej, który ma na celu automatyzację procesu kompilacji programów, na które składa się wiele zależnych od siebie plików. Program czyta reguły zapisane w pliku Makefile i na ich podstawie stwierdza, które pliki wymagają kompilacji. W standardowej paczce istnieją trzy pliki Makefile. Pierwszy, ogólnego przeznaczenia Makefile, drugi, znajdujący się w doc/Makefile, służący do kompilacji plików LaTeX-owych (o tym później), oraz trzeci, znajdujący się w prog/Makefile, który służy do kompilacji rozwiązań. Dokładna specyfikacja nie jest wymagana do korzystania z ułatwień dostarczonych przez program make, więc nie będziemy jej dokładnie omawiać. Poniższa lista zawiera spis najważniejszych komend:
-
make ingen– wygeneruje pliki wejściowe (wymaga puzingen) -
make inwer– sprawdzi poprawność plików wejściowych (wymaga puzinwer) -
make outgen– uruchomi rozwiązanie wzorcowe (puz) na wszystkich testach z folderu in i zapisze wyniki w folderze out -
make run– uruchomi rozwiązanie wzorcowe i wyświetli rezultat na ekranie -
make run_3– uruchomi trzecie rozwiązanie wzorcowe (plik puz3) i wyświetli rezultat na ekranie -
make run_b1– uruchomi pierwsze rozwiązanie błędne (plik puzb1) -
make run_s1– uruchomi pierwsze rozwiązanie wolne (plik puzs1) -
make oirun– uruchomi rozwiązanie wzorcowe, ale skorzysta z sio2jail do oszacowania czasu wykonania (wymaga ustawienia ścieżki do oiejq.sh w makefile.in) -
make report > report.html– wygeneruje raport html, z uruchomienia wszystkich rozwiązań i zapisze rezultat w pliku report.html -
make oireport > oireport.html– analogicznie jak wyżej, jednak do uruchomienia zostanie użyty sio2jail
Uruchamiamy wszystkie powyższe komendy w folderze głównym. Temat generatora i weryfikatora wejść zostanie poruszony w następnym poradniku.
Jednym ze sposobów na zautomatyzowanie procesu tworzenia treści jest użycie języka TeX. Jest on szeroko wykorzystywany przy składaniu tekstów naukowych, ponieważ umożliwia budowanie złożonych wyrażeń, w tym skomplikowanych wzorów matematycznych. Posiada też wiele gotowych pakietów rozwiązujących standardowe problemy związane z tworzeniem publikacji, np. numerowanie równań, automatyczne tworzenie tabel, spisów, skrótów, wstawianie ilustracji. Do przygotowania zadania będziemy używać szablonu sinol.cls. Nie będziemy wyjaśniać co się w nim dzieje, wyjaśnimy tylko sposób użytkowania. Najłatwiej wyjaśnić sposób działania, jak i przydatność tego sposobu, wstawiając przykład. Plikiem TeX, z którego wygenerowaliśmy plik z treści znajduje się tu. Możemy ustawić tam różne wartości na tytuł, id, datę, nazwę konkursu i wiele innych. Standardowo tworzy się główną sekcję, w której następuje opis problemu, potem następuje sekcja wejścia, która jest dokładną specyfikacją wejścia, następnie sekcja wyjścia, która zawiera specyfikacje wyjścia. Potem powinny nastąpić przykłady i sekcja z ocenianiem, precyzująca pod-zadania. Gotowy plik należy nazwać puzzad.tex. Jeśli chcemy stworzyć pliki w kilku wersjach językowych (np. po angielsku), stworzymy drugi plik puzzad-en.tex. Musimy wtedy rozpocząć TeXowy dokument od poniższej linijki.
\documentclass[en]{spiral}Aby je skompilować należy użyć polecenia make znajdując się w katalogu puz/doc. Można też użyć polecenia make clean, aby usunąć pliki powstałe podczas kompilacji.
W końcu możemy przejść do programu weryfikującego wyjście. Program przyjmuje trzy argumenty:
- argv[1] – plik wejściowy
- argv[2] – plik z wyjściem uczestnika
- argv[3] – plik z wzorcowym wyjściem
Najpierw przeczytamy plik z wejściem, żeby dowiedzieć się, o jaki test chodzi. Zrobimy to, korzystając z biblioteki fstream. Zauważmy, że nie musimy zajmować się bezpieczeństwem, ponieważ to my tworzymy pliki wejściowe, więc możemy być pewni ich formatów.
int n;
{
std::ifstream input(argv[1]);
input >> n;
}W ten sposób wczytaliśmy liczbę n, oznaczającą długość boku. Zadanie jest na tyle proste, że na tym etapie można już policzyć rozwiązanie i będzie to krótsze niż wczytywanie dodatkowych danych. W bardziej skomplikowanych zadaniach chcielibyśmy, żeby nasza wzorcówka dostarczyła nam wymiernych informacji o rozwiązaniu. Chociaż w tym przypadku może wydawać się to sztucznym rozwiązaniem, wykorzystamy pierwszą linię wzorcowego wyjścia, żeby stwierdzić, czy rozwiązanie zagadki jest możliwe czy nie.
int modelK;
bool cantDoIt = false;
{
std::ifstream output(argv[3]);
char first;
output >> first;
if (first == 'C') {
cantDoIt = true;
} else {
output.putback(first);
output >> modelK;
}
}Wczytując w ten sposób, patrząc na pierwszy znak wzorcowej odpowiedzi, możemy dowiedzieć się, czy zagadkę da się rozwiązać. Teraz zajmiemy się najtrudniejszą częścią, czyli wczytaniem odpowiedzi użytkownika. Najpierw stworzymy scanner z biblioteki oi.h.
oi::Scanner scanner(argv[2], endf, oi::PL);Teraz wykorzystamy poprzednio zdefiniowaną zmienną cantDoIt, żeby wiedzieć czy powinniśmy spodziewać się słowa, czy liczby. Jeśli zmienna ma wartość true, to powinniśmy uzyskać jedną linię Can't do that. Wczytamy więc jedną linię (czyli wszystkie znaki aż do znaku końca linii) poniższym poleceniem.
int readLen = scanner.readLine(result, resultLen);W readLen została zapisana liczba wczytanych znaków. Jest to istotne ponieważ, mimo że nałożyliśmy ograniczenie górne na długość linii (resultLen), to użytkownik mógł nic nie wypisać na wyjście. Pamiętajmy, że nie powinniśmy karać użytkownika, za pozostawienie białych znaków na końcu linii (i pliku). Wczytamy zatem wszystkie białe znaki, aż do końca pliku.
scanner.skipWhitespaces();Teraz, jeśli wszystko poszło zgodnie z planem, powinien nastąpić znak końca pliku.
if (resultLen == readLen) {
scanner.readEof();
}Widać teraz użyteczność zapisania liczby wczytanych znaków do readLen. Jeśli wczytano maksymalną długość, oznacza to że nie dotarliśmy jeszcze do końca pliku. Jeśli jednak będzie mniejsza, to znaczy że koniec pliku został już osiągnięty. Teraz możemy stwierdzić, czy wczytana linia jest poprawna, używając znanej z C funkcji strcmp.
if (strcmp(cantStr, result) == 0) {
std::cout << "OK" << std::endl;
} else {
std::cout << "WRONG" << std::endl;
std::cout << cantStr << " expected!" << std::endl;
}Jeśli odpowiedź pokrywa się z naszą wzorcową linią, wypiszemy na standardowe wyjście jeden wiersz, zawierający OK. Poinformuje to SIO2, że test został zaliczony poprawnie i można przyznać za niego dodatnią liczbę punktów. Jeśli chcemy dołączyć jakiś komentarz do danego rozwiązania, który będzie widoczny dla uczestnika, powinniśmy zrobić to w drugiej linii. Trzecia linia służy do przydzielenia punktów. Jeśli zostanie pozostawiona pusta, uczestnik otrzyma maksymalny wynik.
Jeżeli linie nie będą identyczne, to wypiszemy w pierwszej linii WRONG, a w następnej komentarz. Pamiętajmy, że niezależnie od wyniku zakończenie programu kodem innym niż 0 będzie skutkować błędem sprawdzaczki na SIO2. Chcemy za wszelką cenę uniknąć takiego rezultatu, ponieważ w ten sam sposób system komunikuje wszelkie wewnętrzne nieprawidłowości. Jeśli zmienna cantDoIt jest ustawiona na false, to w pierwszym wierszu powinna być liczba.
int k = scanner.readInt();
if (k != modelK) {
std::cout << "WRONG" << std::endl;
std::cout << "Wrong number of puzzles!" << std::endl;
exit(0);
}
scanner.skipWhitespacesUntilEOLN();
scanner.readEoln();Schemat postępowania jest bardzo podobny jak poprzednio. Wczytujemy jedną liczbę całkowitą. Jeśli nie pokrywa się z naszą liczbą wzorcową, to przerywamy sprawdzanie. Teraz wczytamy 3 liczby użytkownika. Jest to najbardziej ryzykowna część naszego programu. Wczytamy trzy liczby, a potem będziemy oznaczać w tablicy, które kwadraty zostały pokryte. Jeśli użytkownik poda liczbę spoza zakresu naszej tablicy, a my nie sprawdzimy tego, możemy zacząć zapisywać rzeczy pod miejscami w pamięci do których nie powinniśmy mieć dostępu. Tak więc, w pętli wczytujemy liczby w taki sposób.
int x = scanner.readInt(0, n - 1);
scanner.skipWhitespacesUntilEOLN();
int y = scanner.readInt(0, 2);
scanner.skipWhitespacesUntilEOLN();
int z = scanner.readInt(0, 1);
if (i < k - 1) {
scanner.skipWhitespacesUntilEOLN();
scanner.readEoln();
} else {
scanner.skipWhitespaces();
scanner.readEof();
}Warto zwrócić uwagę na powyższy warunek. Jeśli nie jesteśmy jeszcze w ostatniej linii, to powinniśmy pominąć białe znaki na końcu linii i wczytać znak nowej linii. Jeśli jednak jesteśmy w ostatniej linii to powinniśmy pominąć wszelkie białe znaki, po czym wczytać koniec pliku. Pozwoli nam to odseparować rozwiązania, które po poprawnym wyjściu pozostawiają jakiegoś rodzaju śmieci. A teraz sprawdzimy, czy aby na pewno żaden klocek nie wychodzi poza planszę.
bool checkXY = (grid[x][y] == 0);
if (z == 0) {
if (x == n - 1) {
puzzleOutOfBoard();
}
if (!checkXY || grid[x + 1][y] != 0) {
puzzlesIntesect();
}
} else {
if (y == 2) {
puzzleOutOfBoard();
}
if (!checkXY || grid[x][y + 1] != 0) {
puzzlesIntesect();
}
}Jeśli wszystko jest dobrze, a nasz program nie zakończył się z powodu wywołania jednej z powyższych funkcji, to pozostaje sprawdzić, czy wszystkie pola zostały pokryte. Jeśli k pokrywa się z liczbą w rozwiązaniu wzorcowym, to wiemy że przyznamy co najmniej połowę punktów. Wypisujemy wtedy OK w pierwszej linii. Jeśli chcemy przyznać za test mniej niż 100% punktów, to w trzeciej linii standardowego wyjścia powinna znaleźć się liczba całkowita, oznaczająca procent punktów przyznanych za dany test. Jeśli któreś pole pozostanie odkryte, wypiszemy odpowiedni komunikat i przydzielimy uczestnikowi tylko 50 punktów. Gotową checkerkę można znaleźć w pliku puz/prog/puzchk.cpp. Możemy teraz uruchomić make run i zobaczyć, czy wzorcówka jest dobrze interpretowana przez checkerkę. Dobrym zwyczajem jest napisać wiele rozwiązań wzorcowych i błędnych, które wypisują wyjście w różnej formie. Pozwoli nam to sprawdzić, czy nasza checkerka dobrze rozpoznaje wyjście.