Główne cele pierwszego laboratorium to zapoznanie studentów ze środowiskiem automatycznego sprawdzania programów studenckich oraz porównanie w praktyce wielomianowych złożoności obliczeniowych różnych rzędów - sześciennego, kwadratowego i liniowego.
Rozwiązaniem każdego zadania z laboratorium jest program komputerowy implementujący algorytm dla problemu z tego zadania. Programy do oceny są zgłaszane poprzez portal Szkopuł (https://szkopul.edu.pl/c/laboratorium-z-asd-2019/). Każde zadanie można zgłosić co najwyżej 100 razy. Każde zgłoszenie jest automatycznie oceniane na zestawie wcześniej przygotowanych testów. Wyniki sprawdzenia są wyświetlane na bieżąco. Rozwiązanie zostaje zaakceptowane, jeżeli dla wszystkich testów zwróci poprawny wynik oraz zmieści się w połowie limitu czasowego i w limicie pamięciowym. Limity są tak dobrane, żeby akceptowane były tylko rozwiązania efektywne złożonościowo.
Zadanie BAZ (Bazarek)
Dostępna pamięć: 128MB.
Termin: 27.10.2019, 23:59:59
Mały Bajtek spędza wakacje u babci Bajtuli. Codziennie rano babcia idzie na bazarek, by zakupić pewne produkty. Chłopiec szybko zauważył ciekawą prawidłowość: każdego dnia babcia wydaje na zakupy kwotę wyrażającą się nieparzystą liczbą całkowitą. Bajtek wkrótce ustalił, iż dostrzeżona prawidłowość jest cechą charakterystyczną wszystkich bajtockich babć.
Każdego dnia babcia Bajtula kupuje po co najwyżej jednym egzemplarzu każdego z \( \displaystyle n \) produktów dostępnych na bazarku. Babcia w swej zapobiegliwości nie chce brać na zakupy zbyt dużej sumy pieniędzy. Któregoś dnia poprosiła Bajtka o wskazówkę, ile pieniędzy musi ze sobą zabrać, jeśli tego dnia chce kupić na bazarku dokładnie \( \displaystyle k \) produktów. Niestety Bajtek nie wie, które produkty babcia zamierza kupić, więc zabrana kwota musi wystarczyć na dowolne \( \displaystyle k \) produktów (tak żeby suma ich kosztów była nieparzysta). Ta sama sytuacja powtórzyła się kilkukrotnie. Bajtek postanowił więc podejść do sprawy metodycznie i napisać program, który mając do dyspozycji ceny wszystkich produktów dostępnych na bazarku, będzie odpowiadał na pytania babci.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą \( \displaystyle n \) ( \( \displaystyle 1 \le n \le 1\,000\,000 \) ) oznaczającą liczbę produktów dostępnych na bazarku. Drugi wiersz zawiera \( \displaystyle n \) liczb całkowitych z zakresu \( \displaystyle [1,10^9] \), oznaczających ceny poszczególnych produktów. Liczby te podane są w kolejności niemalejącej.
W trzecim wierszu znajduje się jedna liczba całkowita \( \displaystyle m \) ( \( \displaystyle 1 \le m \le 1\,000\,000 \) ) oznaczająca liczbę dni, które Bajtek spędzi jeszcze u babci. Każdy z kolejnych \( \displaystyle m \) wierszy zawiera jedną liczbę całkowitą \( \displaystyle k_i \) ( \( \displaystyle 1 \le k_i \le n \) ), oznaczającą liczbę produktów, które danego dnia zamierza kupić babcia.
Wyjście
Twój program powinien wypisać na wyjście \( \displaystyle m \) wierszy. W \( \displaystyle i \)-tym wierszu (dla \( \displaystyle i=1,\ldots,m \) ) powinna znaleźć się jedna liczba całkowita, oznaczająca maksymalną nieparzystą cenę \( \displaystyle k_i \) produktów. Jeśli nie da się wybrać \( \displaystyle k_i \) produktów, których łączna cena byłaby nieparzysta, w \( \displaystyle i \)-tym wierszu wyjścia powinna znaleźć się liczba \( \displaystyle -1 \).
Przykład
Dla danych wejściowych:
4
1 2 3 4
3
2
3
4
poprawnym wynikiem jest:
7
9
-1
Zadanie MAT (Matryca)
Dostępna pamięć: 128MB.
Termin: 27.10.2019, 23:59:59
Bajtocki Zakład Poligraficzny (BZP) otrzymał duże zlecenie na produkcję prążkowanych tapet, stanowiących hit sezonu w projektowaniu wnętrz. Każda tapeta składa się z \( \displaystyle n \) jednakowej szerokości barwnych pionowych pasków. BZP ma zająć się zaprojektowaniem oraz wydrukowaniem tapet. Zleceniodawca z założenia określił barwy niektórych pasków na tapecie. W przypadku pozostałych pasków pozostawił BZP pełną dowolność.
Do wydruku tapet w BZP używa się matryc drukujących pewną liczbę kolejnych pasków na tapecie. Matryca ma określone barwy każdego z drukowanych pasków i może być krótsza niż cała tapeta. Jeśli matryca składa się z \( \displaystyle k \) pasków, przykłada się ją we wszystkich \( \displaystyle n-k+1 \) możliwych pozycjach, na których jej paski pokrywają się z paskami tapety, za każdym razem drukując wszystkie paski matrycy. W ten sposób jeden pasek tapety może zostać zadrukowany więcej niż raz. W przypadku, gdy dany pasek zostanie zadrukowany różnymi barwami, jego ostateczny kolor będzie stanowił mieszankę tych barw.
Pracownicy BZP, niezależnie od posiadanego wyczucia estetyki, chcieliby przede wszystkim zaprojektować możliwie najkrótszą matrycę, która pozwoli wydrukować całą tapetę. Muszą oni pamiętać o tym, że w przypadku pasków określonych przez zleceniodawcę muszą użyć czystej barwy, bez domieszki innych barw. Innymi słowy, przy każdym przyłożeniu matrycy pokrywającym taki pasek, barwa paska na matrycy musi być dokładnie taka, jak określona przez zleceniodawcę.
Wejście
Jedyny wiersz wejścia zawiera napis złożony z wielkich liter alfabetu łacińskiego oraz gwiazdek (*), określający oczekiwany wygląd tapety. Poszczególne litery oznaczają różne barwy pasków, natomiast gwiazdki oznaczają paski, których barwa nie została określona przez zleceniodawcę. Długość napisu \( \displaystyle n \) spełnia \( \displaystyle 1 \le n \le 1\,000\,000 \).
Wyjście
Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą \( \displaystyle k \): minimalną długość matrycy, która pozwala wydrukować żądaną tapetę.
Przykład
Dla danych wejściowych:
A*B*B*A
poprawnym wynikiem jest:
6
Wyjaśnienie do przykładu: Matryca o długości 6 pozwalająca wydrukować przedstawioną na wejściu tapetę (złożoną z siedmiu pasków) to ABBBBA.