Juror

Limit pamięci: 128 MB

W tym zadaniu wcielasz się w jurora Olimpiady Informatycznej. Pracujesz właśnie nad przygotowaniem testów do jednego z zadań. Znalazłaś/znalazłeś wadliwe rozwiązanie i teraz musisz przygotować testy, których to rozwiązanie nie przejdzie. Niniejsze zadanie składa się z trzech podzadań. Twoim zadaniem jest napisanie jednego programu, który na podstawie danych wejściowych zorientuje się, z którym podzadaniem ma do czynienia, i znajdzie rozwiązanie dla tego podzadania.

Ponieważ Twoje rozwiązania będą generować testy, powinny one wypisywać dane w dokładnie takim formacie, jak w podanej specyfikacji. Należy zadbać o odpowiednie wypisywanie odstępów i znaków nowego wiersza. W szczególności, na końcu wyjścia należy zawsze wypisać dokładnie jeden znak nowego wiersza.

Pliki do zadania

• quicksort.cpp
• dijkstra_wolna.cpp
• dijkstra_poprawna.cpp
• bfs_poprawny.cpp

W powyższych plikach znajdują się kody źródłowe, o których mowa w dalszej części.

Uwaga. Za to zadanie można zdobyć w sumie punktów.

Podzadanie 1. (50 punktów)

W zadaniu dany jest ciąg liczb całkowitych, który należy posortować. W pliku quicksort.cpp znajduje się rozwiązanie, które implementuje algorytm Quicksort. To rozwiązanie, z powodu użytego sposobu wyboru elementu dzielącego, może działać wolno. Twoim zadaniem jest napisanie programu, który generuje takie testy, dla których łączna liczba iteracji dwóch wewnętrznych pętli while w funkcji quicksort będzie równa co najmniej .

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się słowo sortowanie, po którym następuje liczba ().

Wyjście

Twój program powinien wypisać dane wejściowe dla programu quicksort.cpp w następującym formacie. W pierwszym wierszu wyjścia powinna znaleźć się liczba wczytana z wejścia. W drugim wierszu powinien znaleźć się ciąg liczb całkowitych ().

Podzadanie 2. (50 punktów)

W zadaniu dana jest kwadratowa plansza o wymiarach złożona z kwadratowych pól. Po planszy porusza się pionek. W każdym ruchu pionek może przesunąć się na jedno z czterech pól sąsiadujących z polem, na którym aktualnie się znajduje. Niektóre pola planszy są zabronione i pionek nie może się nigdy na nich znaleźć. Pozostałe pola nazywamy polami dostępnymi. Celem zadania jest obliczenie, dla każdego pola dostępnego, w ilu ruchach pionek może się na nie dostać. Poprawne rozwiązanie tego zadania znajduje się w pliku bfs_poprawny.cpp. Zawiera ono implementację algorytmu BFS na podstawie szablonu queue z STL.

Łatwo jednak popełnić pewien (nieoczywisty) błąd i w rozwiązaniu użyć takiej implementacji kolejki, która zakłada, że każdym momencie w kolejce będzie co najwyżej elementów. W tym podzadaniu Twój program powinien wypisać test, dla którego powyższa procedura w pewnym momencie w trakcie wykonania będzie przechowywać w kolejce więcej niż elementów.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się słowo bfs, po którym następuje liczba ().

Wyjście

Twój program powinien wypisać dane wejściowe dla programu bfs_poprawny.cpp w następującym formacie. Pierwszy wiersz powinien zawierać liczbę wczytaną z wejścia, a następnie dwie liczby i (). Oznaczają one, że pionek startuje na polu w wierszu i kolumnie .

Dalej powinien znajdować się opis planszy w postaci wierszy po znaków # i/lub . - znaki te oznaczają odpowiednio pole zabronione i pole dostępne. Pole startowe musi być polem dostępnym.

Dla podanej planszy, w programie bfs_poprawny.cpp do kolejki powinno być wstawione więcej niż elementów.

Podzadanie 3. (50 punktów)

W zadaniu należy napisać algorytm znajdujący najkrótsze ścieżki w grafie nieskierowanym, w którym krawędzie mają długości wyrażone dodatnimi liczbami całkowitymi. Graf składa się z wierzchołków, które numerujemy . Celem jest znalezienie odległości od wierzchołka do każdego wierzchołka grafu. Poprawne rozwiązanie znaleźć można w pliku dijkstra_poprawna.cpp. Implementuje ono (nieco zmodyfikowany) algorytm Dijkstry przy użyciu priority_queue, czyli kolejki priorytetowej z STL.

Krótki opis modyfikacji.

W książkowej wersji algorytmu Dijkstry dla każdego nieodwiedzonego wierzchołka, do którego znaleźliśmy już pewną ścieżkę, pamiętamy długość tej ścieżki w kolejce priorytetowej i tę wartość aktualizujemy. Modyfikacja w załączonym kodzie polega na tym, że w sytuacji, gdy znajdziemy nową, krótszą ścieżkę do danego wierzchołka, po prostu dodajemy nowy element do kolejki priorytetowej. Element kolejki, który reprezentuje poprzednią wartość, od tego momentu staje się "śmieciem" w kolejce, dlatego przy usuwaniu elementów z kolejki sprawdzamy, czy nie natrafiamy na "śmieć", i ewentualnie pomijamy jego przetwarzanie (patrz instrukcja break w kodzie).

Jeden z błędów, jaki można tu popełnić, to użycie zwykłej kolejki w miejscu kolejki priorytetowej. Taka implementacja znajduje się w pliku dijkstra_wolna.cpp. Wprawdzie jest ona poprawna, jednak czasem działa znacznie wolniej.

Twoim zadaniem jest napisanie programu, który będzie generować testy, dla których wewnętrzna pętla for w drugim programie wykona co najmniej 20 razy więcej obrotów niż analogiczna pętla w pierwszym programie.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się słowo sciezki, po którym następuje liczba całkowita ().

Wyjście

Twój program powinien wypisać wejście dla programów dijkstra_poprawna.cpp oraz dijkstra_wolna.cpp w następującym formacie. W pierwszym wierszu wyjścia powinny znaleźć się: liczba wczytana z wejścia oraz liczba całkowita (). Liczba oznacza liczbę wierzchołków, zaś - liczbę krawędzi grafu. W kolejnych wierszach powinny znaleźć się opisy poszczególnych krawędzi grafu. Opis jednej krawędzi powinien składać się z trzech liczb całkowitych , , (, , ). Dla każdych dwóch wierzchołków może istnieć co najwyżej jedna krawędź, która je łączy. Każda krawędź grafu powinna zostać wypisana dokładnie raz. Musi istnieć co najmniej jedna krawędź o końcu w wierzchołku .

Autor zadania: Jakub Łącki.