Poniżej przypominamy zasady zaliczania laboratorium z ASD związane z zadaniem karnym oraz przedstawiamy archiwum zadań karnych z ubiegłych lat.
Kiedy powinienem rozwiązać zadanie karne?
W Górach Bitockich zorganizowano ciekawe zawody. Każdy zawodnik zaczyna w wybranym przez siebie schronisku i pokonuje wybraną przez siebie trasę, poruszając się po szlakach turystycznych. Dla każdego schroniska określono liczbę punktów przysługujących za dotarcie do niego. To samo schronisko można odwiedzać wielokrotnie, lecz punkty naliczane są tylko za pierwsze odwiedzenie. Celem jest zdobycie maksymalnej liczby punktów w ciągu jednej doby.
Sprawę nieco komplikuje fakt, że na mocy decyzji Bitockiego Parku Narodowego, po wielu szlakach można poruszać się tylko w jednym kierunku. Z tego powodu odwiedzenie wszystkich schronisk może być niemożliwe. Ponadto, niektóre szlaki wiodą jaskiniami i mogą przechodzić pod szlakami na powierzchni, a więc graf szlaków niekoniecznie jest planarny.
Słynna bajtocka turystka Ula Speck trenowała ciężko cały rok i zamierza wygrać te zawody. Dzięki morderczemu treningowi Ula wie, że jest w stanie przejść każdą trasę w Górach Bitockich w ciągu doby. Ula zwróciła się do Ciebie, abyś zaplanował jej trasę umożliwiającą zdobycie maksymalnej możliwej liczby punktów.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite \( \displaystyle n \) i \( \displaystyle m \) ( \( \displaystyle 1 \leq n \leq 200\,000 \), \( \displaystyle 0 \leq m \leq 1\, 000\,000 \) ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę schronisk i liczbę jednokierunkowych szlaków. (Szlaki dwukierunkowe modelowane są za pomocą dwóch szlaków jednokierunkowych.) W kolejnych \( \displaystyle n \) wierszach podano punkty przysługujące odwiedzaniu schronisk. W \( \displaystyle (i+1) \)-szym wierszu została zapisana liczba całkowita \( \displaystyle p_i \) ( \( \displaystyle 0\le p_i \le 5\,000 \) ) oznaczająca liczbę punktów przysługujących za pierwsze odwiedzenie \( \displaystyle i \)-tego schroniska. W każdym z kolejnych \( \displaystyle m \) wierszy znajduje się opis jednego ze szlaków: para oddzielonych pojedynczym odstępem liczb całkowitych \( \displaystyle a \) i \( \displaystyle b \) ( \( \displaystyle 1 \leq a, b \leq n \) ), oznacza szlak od schroniska \( \displaystyle a \) do schroniska \( \displaystyle b \).
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać maksymalną możliwą do zdobycia liczbę punktów, którą można uzyskać odwiedzając schroniska na pojedynczej trasie.
Przykład
Dla danych wejściowych:
6 7
1
1
2
3
1
2
4 5
2 3
1 2
6 2
2 5
2 4
4 2
poprawnym wynikiem jest:
8
Słowo jest palindromem wtedy i tylko wtedy, gdy jest takie samo, jeśli czytamy je wspak. Podpalindromem słowa \( \displaystyle v \) nazywamy dowolny palindrom powstający przez usunięcie z \( \displaystyle v \) pewnej liczby (niekoniecznie sąsiednich) liter. Napisz program, który znajduje długość najdłuższego podpalindromu podanego słowa \( \displaystyle v \).
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita \( \displaystyle n \) ( \( \displaystyle 1 \le n \le 5\,000 \) ), będąca długością słowa. Drugi wiersz zawiera \( \displaystyle n \)-literowe słowo składające się wyłącznie z małych liter alfabetu angielskiego.
Wyjście
Jedyny wiersz wyjścia powinien zawierać długość najdłuższego podpalindromu danego słowa.
Przykład
Dla danych wejściowych:
11
jakitokajak
poprawnym wynikiem jest:
7
Firma Bajtazar i Syn produkuje sprzęt AGD najwyższej jakości. Po zdjęciu sprzętu z linii produkcyjnej musi on zostać przetransportowany do odpowiedniego magazynu, skąd rusza w dalszą drogę do klienta. Ze względu na wagę produkowanego sprzętu zatrudnianie w tym celu robotników jest czasochłonne i mało ekonomiczne. Firma Bajtazar i Syn zdecydowała się zatem zautomatyzować ten proces. Na początek zakupiono dwa roboty sterowane radiem. Mogą się one przemieszczać pomiędzy określonymi pozycjami w fabryce (węzłami). W węzłach znajdują się między innymi linie produkcyjne i magazyny. W zależności od zagospodarowania przestrzennego fabryki pomiędzy węzłami znajduje się przejście lub nie, przy czym jeżeli można przejść z węzła \( \displaystyle q \) do węzła \( \displaystyle p \), to można też przejść z węzła \( \displaystyle p \) do węzła \( \displaystyle q \). Sterowanie radiem pociąga za sobą dwa ograniczenia: roboty nie mogą poruszać się równocześnie, czyli każde polecenie z radia skutkuje przemieszczeniem jednego z robotów do sąsiedniego węzła, oraz aby zagwarantować właściwy odbiór roboty muszą w każdym momencie zachować określony dystans pomiędzy sobą. Dystans definiujemy jako najkrótszą drogę pomiędzy węzłami.
Mając dane dwie pary węzłów, gdzie każda para określa linię produkcyjną i odpowiadający jej magazyn, wyznacz najkrótszą drogę robotów pozwalającą przetransportować towar.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne \( \displaystyle n \) i \( \displaystyle k \) ( \( \displaystyle 1 \leq n \leq 2500 \), \( \displaystyle 1 \leq k \leq n-1 \) ) oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę węzłów oraz wymagany odstęp robotów. Przyjmujemy, że węzły ponumerowane są liczbami od \( \displaystyle 0 \) do \( \displaystyle n-1 \). W kolejnych dwóch wierszach podane są dwie pary węzłów \( \displaystyle a \), \( \displaystyle b \) oraz \( \displaystyle c \), \( \displaystyle d \). Robot \( \displaystyle X \) powinien przemieścić się z linii produkcyjnej w węźle \( \displaystyle a \) do magazynu w węźle \( \displaystyle b \). Analogicznie robot \( \displaystyle Y \) winien przemieścić się z węzła \( \displaystyle c \) do węzła \( \displaystyle d \). Każde polecenie z radia skutkuje przemieszczeniem jednego z robotów do sąsiedniego węzła. Każdy z kolejnych \( \displaystyle n \) wierszy odpowiada węzłowi \( \displaystyle i \in [0,n-1] \). Każdy zaczyna się liczbą \( \displaystyle l(i) \), a następnie podane jest \( \displaystyle l(i) \) ( \( \displaystyle 0 \leq l(i) \leq 50 \) ) numerów odpowiadających węzłom osiągalnym z \( \displaystyle i \) (a zatem również \( \displaystyle i \) jest osiągalne ze wszystkich tych węzłów).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać minimalną łączną liczbę ruchów robotów pozwalającą je przemieścić lub \( \displaystyle -1 \), jeśli robotów przemieścić się nie da.
Przykład
Dla danych wejściowych:
5 2
0 2
2 4
1 1
1 2
1 3
1 4
1 0
poprawnym wynikiem jest:
4
Wyjaśnienie do przykładu:
Zadany graf jest cyklem o 5 węzłach. Robot \( \displaystyle X \) idzie z 0 do 2, zaś robot \( \displaystyle Y \) z 2 do 4. Optymalne przemieszczenie robotów:
Profesor Makary przyjechał właśnie do górskiego kurortu na urlop zimowy. Niestety w tym roku pogoda nie sprzyja narciarzom, dlatego profesor postanowił spędzić czas, wędrując po górach. Właśnie ogląda mapę, na której zaznaczono \( \displaystyle n \) szczytów połączonych za pomocą \( \displaystyle m \) dwukierunkowych szlaków. W czasie zimy w górach należy zachować szczególną ostrożność, dlatego profesor chciałby unikać wędrowania na zbyt dużej wysokości. Szczęśliwie, dla każdego szlaku na mapie zaznaczone jest, ile metrów nad poziomem morza znajduje się najwyższy punkt z danego szlaku.
Profesor planuje teraz \( \displaystyle k \) wędrówek między szczytami gór. Dla każdej z tych wędrówek chciałby poznać minimalną liczbę \( \displaystyle M \), taką że cała trasa wędrówki będzie prowadzić nie wyżej niż \( \displaystyle M \) metrów nad poziomem morza.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite \( \displaystyle n \), \( \displaystyle m \) oraz \( \displaystyle k \) ( \( \displaystyle 2 \leq n \leq 5\,000 \), \( \displaystyle 1 \leq m \leq 500\,000 \), \( \displaystyle 1 \leq k \leq 10\,000 \) ), oznaczające kolejno liczbę szczytów górskich, liczbę łączących je szlaków oraz liczbę wędrówek, które planuje profesor. Szczyty górskie są ponumerowane od \( \displaystyle 1 \) do \( \displaystyle n \).
W każdym z następnych \( \displaystyle m \) wierszy znajduje się opis jednego szlaku w postaci trzech liczb całkowitych \( \displaystyle a_i \), \( \displaystyle b_i \) i \( \displaystyle c_i \) ( \( \displaystyle 1 \leq a_i, b_i \leq n \), \( \displaystyle a_i \neq b_i \), \( \displaystyle 1 \leq c_i \leq 100\,000 \) ). Oznaczają one, że szczyty górskie \( \displaystyle a_i \) oraz \( \displaystyle b_i \) połączone są szlakiem, którego najwyższy punkt znajduje się \( \displaystyle c_i \) metrów nad poziomem morza. Każde dwa szczyty będą połączone co najwyżej jednym szlakiem. Pomiędzy dowolną parą szczytów można przejść, korzystając ze szlaków.
Następne \( \displaystyle k \) wierszy opisuje wędrówki planowane przez profesora. W \( \displaystyle i \)-tym z tych wierszy znajdują się dwie liczby całkowite \( \displaystyle p_i \), \( \displaystyle q_i \) ( \( \displaystyle 1 \leq p_i, q_i \leq n \), \( \displaystyle p_i \neq q_i \) ). Oznaczają one, że w trakcie \( \displaystyle i \)-tej wędrówki profesor chciałby przejść ze szczytu o numerze \( \displaystyle p_i \) do szczytu o numerze \( \displaystyle q_i \).
Wyjście
Twój program powinien wypisać na standardowe wyjście \( \displaystyle k \) wierszy, po jednym dla każdej planowanej wędrówki. W \( \displaystyle i \)-tym z tych wierszy powinna znaleźć się liczba \( \displaystyle M_i \) - najmniejsza liczba całkowita, taka że między szczytami \( \displaystyle p_i \) oraz \( \displaystyle q_i \) można przejść, nie wchodząc nigdy na wysokość większą niż \( \displaystyle M_i \) metrów nad poziomem morza.
Przykład
Dla danych wejściowych:
5 7 4
2 5 10
5 1 2
1 2 1
5 3 200
4 1 3
2 4 3
1 3 100
3 5
5 4
2 1
2 4
poprawnym wynikiem jest:
100
3
1
3
Pojedynczą zmianą w słowie nazwiemy:
Mając dane dwa słowa, oblicz, ilu co najmniej pojedynczych zmian wymaga przekształcenie pierwszego słowa w drugie. Możesz założyć, że liczba ta jest nie większa niż \( \displaystyle 100 \).
Wejście
Standardowe wejścia składa się z dwóch wierszy, w których zapisane są dwa słowa \( \displaystyle X \) i \( \displaystyle Y \) (składające się z liter alfabetu angielskiego 'A'-'Z') o długości nie większej niż \( \displaystyle 1\,000\,000 \) znaków.
Wyjście
Na standardowe wyjście Twój program powinien wypisać jedną liczbę całkowitą, będącą minimalną liczbą zmian, której wymaga przekształcenie \( \displaystyle X \) w \( \displaystyle Y \).
Przykład
Dla danych wejściowych:
ABCFD
BCGDE
poprawnym wynikiem jest:
3
Wyjaśnienie: Przykładowe przekształcenie: \( \displaystyle \mathtt{ABCFD} \to \mathtt{ABCGD} \to \mathtt{BCGD} \to \mathtt{BCGDE} \).
Profesor Makary. Znowu ma kłopoty. Ale chyba niczego innego się nie spodziewaliście?
Przyjaciel profesora, ten mieszkający na wsi i wyznaczający procent cukru w cukrze, znalazł wreszcie źródło doskonałego cukru. Niestety, występuje on w wielu postaciach, a jeszcze nie wiadomo, które zainteresują konsumentów. Profesor opracował zestaw reakcji chemicznych, z których każda przekształca jedną postać cukru w inną.
Reakcje zachodzą według następujących reguł:
Dla danej postaci początkowej profesor chciałby wiedzieć, do ilu innych postaci można z niej przekształcić cukier, używając do tego znanych profesorowi reakcji. Profesora interesują tylko te substancje, z których można powrócić do postaci początkowej, tak żeby w procesie otrzymywania i powrotu do substancji początkowej była parzysta liczba reakcji odwracających.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite: \( \displaystyle n \) ( \( \displaystyle 1 \le n \le 10\,000 \) ) oznaczająca liczbę znanych postaci cukru i \( \displaystyle m \) ( \( \displaystyle 1 \le m \le 100\,000 \) ) - liczba znanych reakcji. Kolejne \( \displaystyle m \) wierszy to opisy reakcji, każdy z nich składa się z trzech liczb: \( \displaystyle S_1 \), \( \displaystyle S_2 \), \( \displaystyle o \), oznaczających odpowiednio substancję, którą się przekształca ( \( \displaystyle 1 \le S_1 \le n \) ), substancję wynikową ( \( \displaystyle 1 \le S_2 \le n \) ) oraz to, czy reakcja jest odwracająca ( \( \displaystyle o=1 \) ), czy nie ( \( \displaystyle o=0 \) ). Kierunek opisanej reakcji jest właściwy dla sytuacji przed wykonaniem pierwszej reakcji odwracającej.
Wyjście
Wyjście powinno składać się z \( \displaystyle n \) wierszy. W \( \displaystyle i \)-tym z nich należy wypisać, ile postaci cukru daje się otrzymać z postaci o numerze \( \displaystyle i \).
Przykład
Dla danych wejściowych:
5 5
1 2 1
2 4 0
3 2 0
3 5 1
4 3 0
poprawnym wynikiem jest:
3
3
3
3
0
Wyjaśnienie do przykładu: Na rysunku (patrz załącznik do laboratorium) krawędzie przerywane to reakcje odwracające. Z substancji 1 można stworzyć substancje 2, 3 i 4, tak że z każdej z nich można wrócić do substancji 1, wykonując łącznie parzyście wiele reakcji odwracających, np. zgodnie ze schematem \( \displaystyle 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \). Dalej, z substancji 2 można stworzyć substancje 3, 4 i 5,
z 3: 2, 4, 5, z 4: 2, 3 i 5, a z 5 nie można otrzymać żadnej innej substancji.
Profesor Makary zwiedzał Muzeum Domina. W jednej z sal był ułożony w tradycyjny sposób (każde dwa sąsiadujące klocki mają tę samą liczbę oczek na sąsiadujących połówkach) bardzo długi wąż. Profesor, w sobie tylko znany sposób, rozwalił wszystkie kostki po całej sali, po czym zaczął układać łańcuch ponownie. Niestety nie wychodziło mu to i zaczął się zastanawiać, czy na pewno odnalazł wszystkie klocki domina. Pomóż profesorowi (przecież musi on jeszcze nocami malować autostradę).
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita \( \displaystyle n \) ( \( \displaystyle 0\le n \le 1\,000\,000 \) ) oznaczająca liczbę znalezionych klocków domina. W każdym z następnych \( \displaystyle n \) wierszy znajdują się dwie liczby całkowite \( \displaystyle 0\le a_i, b_i \le 10\,000 \) będące liczbami oczek na poszczególnych kostkach.
Wyjście
Twój program powinien wypisać na standardowe wyjście, ile, co najmniej, kostek domina zgubił profesor.
Przykład
Dla danych wejściowych:
3
2 1
2 3
4 5
poprawnym wynikiem jest:
1
| Załącznik | Wielkość |
|---|---|
| prozad1.png | 18.02 KB |
