Delta mi!

Neon składa się z dwóch słów. Na ile sposobów można zgasić niektóre litery w neonie, tak by litery, które pozostaną zapalone, w obu słowach układały się w ten sam niepusty podciąg? Ile różnych podciągów da się w ten sposób uzyskać?

Weźmy wypukły -kąt. Na początku żadna przekątna nie jest narysowana. Zadaniem jest opracowanie struktury danych, która umożliwi optymalne obsłużenie zapytań:

•

Sprawdź — sprawdza, czy między punktami i jest narysowana przekątna,

•

Dodaj — rysuje przekątną pomiędzy punktami i  — o ile nie przecina ona żadnej innej narysowanej przekątnej,

•

Usuń — usuwa przekątną między punktami i 

Dana jest triangulacja n-kąta wypukłego za pomocą nieprzecinających się przekątnych. Jeden z trójkątów tej triangulacji jest pomalowany na czarno. Dwaj gracze na przemian odcinają od wielokąta po jednym trójkącie. Gracz, który odetnie czarny trójkąt, wygrywa. Na wejściu mamy liczbę n oraz opis triangulacji w postaci listy trójek definiujących kolejne trójkąty (wierzchołki wielokąta są ponumerowane kolejno od 1 do n). Czarny trójkąt jest wymieniony jako pierwszy. Musimy odpowiedzieć na pytanie: który gracz ma strategię wygrywającą?

Wiejski listonosz roznosi pocztę po okolicy. Każda wieś leży przy drodze albo na przecięciu dwóch lub czterech dróg, zatem można z niej wyjść w 2, 4 lub 8 kierunkach (niektóre drogi mogą prowadzić ze wsi do niej samej, a pomiędzy dwiema wsiami może być więcej niż jedna bezpośrednia droga). Budynek poczty jest w jednej ze wsi. Listonosz musi odwiedzić wszystkie wsie, a ponadto musi przejść wzdłuż wszystkich dróg (przy nich też stoją domy) i wrócić na pocztę. Za przejście każdej mili poczta płaci listonoszowi 1EUR. Ponadto mieszkańcy każdej wsi chcą, aby listonosz odwiedził ich jak najwcześniej, dlatego poczta zawarła z każdą ze wsi (wsie numerujemy liczbami ) umowę, w której określona jest pewna liczba : mianowicie, jeśli listonosz odwiedzi wieś numer jako -tą w kolejności (tzn. odwiedził wcześniej dokładnie różnych innych wsi) oraz to wieś dopłaca poczcie EUR, a jeśli to poczta karnie płaci wsi EUR. Jak wyznaczyć trasę listonosza, aby zmaksymalizować zysk (ew. zminimalizować stratę) poczty? Na wejściu mamy daną liczbę wsi , opis grafu dróg i umówione wartości ,

Rozważamy pewne państwo podzielone na  województw i zawierające  miast. W tym państwie jest  dróg, z których każda łączy jakąś parę miast. Naszym zadaniem jest tak wybrać stolice województw, aby każde województwo miało dokładnie jedną stolicę (będącą jednym z miast tegoż województwa), a każda z dróg miała jakąś stolicę na co najmniej jednym swym końcu. Wiadomo, że każda droga łączy dwa różne miasta, każde województwo zawiera co najmniej jedno miasto, a każde miasto należy do dokładnie jednego województwa.

Mamy do dyspozycji kamiennych bloków różnych rozmiarów. Mamy obliczyć, na ile sposobów można zbudować z tych bloków wieżę, jeżeli należy użyć ich wszystkich, a jeden blok można położyć na drugim tylko wtedy, gdy rozmiar górnego jest nie większy niż rozmiar dolnego powiększony o ustaloną liczbę dodatnią Wynik należy zwrócić modulo jakaś nieduża liczba całkowita.

W nowo powstałej szkole wybudowano s sal wykładowych, zatrudniono nauczycieli i ogłoszono nabór do klas. W szkole będzie nauczanych  przedmiotów. Każdy przedmiot ma przypisanego nauczyciela, który będzie go wykładał, oraz klasę, która będzie na te wykłady uczęszczała. Każdego dnia na dany przedmiot ma być przeznaczona jedna godzina lekcyjna. Należy wyznaczyć plan zajęć w szkole, tak by zminimalizować czas, w którym w szkole przebywają uczniowie.