In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
Uwaga. Za to zadanie można zdobyć w sumie 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 .
W pierwszym i jedynym wierszu wejścia znajduje się słowo sortowanie, po którym następuje liczba ().
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 ().
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.
W pierwszym i jedynym wierszu wejścia znajduje się słowo bfs, po którym następuje liczba ().
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.
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.
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.
W pierwszym i jedynym wierszu wejścia znajduje się słowo sciezki, po którym następuje liczba całkowita ().
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.