Laboratoria

Laboratorium 1: złożoność obliczeniowa w praktyce

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

Wskazówki dla studentów

Jak rozwiązać to zadanie w złożoności $ \displaystyle O(n) $ w przypadku, gdy żądana suma nie musi być nieparzysta?
W rozwiązaniu oryginalnego zadania skorzystajmy z poprzedniego rozwiązania. Jeśli suma $ \displaystyle k $ najdroższych przedmiotów wyszła nieparzysta, to mamy rozwiązanie. Jeśli zaś wyszła parzysta, w jaki sposób zmodyfikować wybór $ \displaystyle k $ przedmiotów, by otrzymać jak najwyższą sumę, ale już nieparzystą? Zaproponuj rozwiązania o złożoności $ \displaystyle O(n^2) $ i $ \displaystyle O(n) $.

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.

Wskazówki dla studentów

Jak sprawdzić w czasie $ \displaystyle O(n) $, czy matryca może mieć konkretną długość $ \displaystyle m $?
Zastosuj wyszukiwanie binarne, aby otrzymać rozwiązanie o złożoności $ \displaystyle O(n \log n) $.
Zadanie ma także (prostsze) rozwiązanie liniowe.

Laboratorium 2: programowanie dynamiczne

Zadanie z drugiego laboratorium pomaga lepiej zapoznać się z techniką programowania dynamicznego.

Zadanie SOR (Sortowanie komórkowe)

Dostępna pamięć: 64MB.

Sortowanie komórkowe jest bardzo ciekawym algorytmem o dużej jak na sortowanie złożoności czasowej. Algorytm ten działa krokowo, to znaczy wykonuje na danym ciągu pewien krok (sekwencję operacji), aż ciąg stanie się posortowany niemalejąco.

Krok sortowania wygląda tak, że analizujemy ciąg od lewej do prawej i na boku budujemy ciąg wynikowy kroku. Na początku do ciągu wynikowego wkładamy pierwszy element aktualnego ciągu, a następnie każdy kolejny element umieszczamy na początku ciągu pomocniczego, jeżeli poprzedni element oryginalnego ciągu był od niego większy, na końcu zaś, jeżeli poprzedni był od niego mniejszy. Dla przykładu, w jednym kroku algorytmu z ciągu: 5, 6, 2, 1, 4, 3 powstają kolejno ciągi pomocnicze:

5,
5, 6,
2, 5, 6,
1, 2, 5, 6,
1, 2, 5, 6, 4,
3, 1, 2, 5, 6, 4,

a ostatni z nich jest wynikiem działania tego kroku algorytmu.

Twoim zadaniem jest ,,odsortować'' dany ciąg, czyli stwierdzić, ile różnych ciągów zmienia się w ten właśnie ciąg w jednym kroku algorytmu.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \le n \le 1000 $ ). Drugi wiersz zawiera ciąg $ \displaystyle n $ parami różnych liczb całkowitych ze zbioru $ \displaystyle \{1,\dots,n\} $, reprezentujących ciąg, który należy odsortować.

Wyjście
Należy wypisać resztę z dzielenia przez $ \displaystyle 10^9 $ liczby różnych ciągów, które w jednym kroku sortowania komórkowego przechodzą na dany ciąg.

Przykład

Dla danych wejściowych:
4
1 2 3 4
poprawnym wynikiem jest:
8
natomiast dla danych wejściowych:
4
4 3 2 1
poprawnym wynikiem jest:
0

Wyjaśnienie do przykładu:
W jednym kroku algorytmu sortowania na ciąg 1, 2, 3, 4 przechodzą ciągi:

1, 2, 3, 4,
4, 3, 2, 1,
2, 1, 3, 4,
3, 2, 1, 4,
2, 3, 1, 4,
2, 3, 4, 1,
3, 4, 2, 1,
3, 2, 4, 1,

natomiast na ciąg 4, 3, 2, 1 nie przechodzi żaden inny ciąg liczb.

Wskazówki dla studentów

Zastosuj technikę programowania dynamicznego. Rozwiązanie będzie miało złożoność $ \displaystyle O(n^2) $.
Który element podanego ciągu mógł być ostatnim elementem początkowego ciągu w kroku sortowania? Od czego to zależy?
Pytanie otwarte: czemu podany algorytm w ogóle poprawnie sortuje podany ciąg liczb? Jaka jest jego złożoność czasowa?

Laboratorium 3: proste techniki

Zadanie MEC (Mecze)

Dostępna pamięć: 128 MB.

W treningu piłkarskim uczestniczy $ \displaystyle n $ zawodników ( $ \displaystyle n $ jest liczbą parzystą). W każdym meczu grają wszyscy zawodnicy, po $ \displaystyle n/2 $ w każdej drużynie. Trener postanowił w taki sposób ułożyć składy drużyn, aby każdych dwóch zawodników miało szansę zagrać przeciwko sobie w jakimś meczu (tzn. choć raz zagrać w przeciwnych drużynach).

Trener zaproponował już składy na najbliższe $ \displaystyle m $ meczów. Pomóż mu stwierdzić, czy udało mu się zrealizować jego zamierzenie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 4 \le n \le 40\,000 $, $ \displaystyle 1 \le m \le 50 $ ) oznaczające liczbę zawodników oraz liczbę zaplanowanych meczów. Zawodników numerujemy liczbami od 1 do $ \displaystyle n $.

Każdy z kolejnych $ \displaystyle m $ wierszy zawiera po $ \displaystyle n $ parami różnych liczb całkowitych z zakresu od 1 do $ \displaystyle n $ opisujących składy drużyn na poszczególne mecze. Pierwsze $ \displaystyle n/2 $ liczb w każdym wierszu to numery zawodników grających w pierwszej drużynie, a drugie $ \displaystyle n/2 $ liczb - numery zawodników wchodzących w skład drugiej drużyny.

Wyjście

Twój program powinien wypisać na wyjście jedno słowo TAK lub NIE, w zależności od tego, czy każda para zawodników zagra przeciwko sobie co najmniej w jednym meczu, czy też nie.

Przykład

Dla danych wejściowych:
6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 6 4 5 3
poprawnym wynikiem jest:
TAK

a dla danych wejściowych:
6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 3 4 5 6
poprawnym wynikiem jest:
NIE

Wyjaśnienie do przykładu: W pierwszym przykładzie każda para zawodników gra w przeciwnych drużynach w jednym meczu (np. zawodnicy o numerach 1 i 6), w dwóch meczach (np. zawodnicy 1 i 2) lub nawet we wszystkich trzech meczach (np. zawodnicy 1 i 3). W drugim przykładzie zawodnicy o numerach 2 i 3 zawsze grają w tej samej drużynie.

Wskazówki dla studentów

Skoncentruj się na sprawdzeniu, czy istnieje dwóch zawodników, którzy nigdy nie grali w różnych drużynach. Zastosuj pomysł etykietowania.

Zadanie zaliczeniowe 1

Do tego zadania nie będzie wskazówek. Zadanie należy rozwiązywać samodzielnie. Oprócz akceptacji programu w portalu Szkopuł, należy uzyskać akceptację laboranta.

Zadanie KRE (Kreatywna Księgowość), r. akad. 2017/2018

Dostępna pamięć: 128MB.

Bajtazar zaczął pracę w firmie Kreatywna Księgowość sp. z o.o. Jak sama nazwa wskazuje, księgowość w tej firmie jest bardzo dynamiczna. Do pomocy w utrzymywaniu ksiąg potrzebna będzie mu Twoja pomoc.

Pierwszego dnia pracy Bajtazar otrzymał bilans przychodów firmy z podziałem na kolejne miesiące zapisany w tablicy $A[1 \ldots n]$, gdzie $ A[i] $ oznacza przychody w $ i $-tym miesiącu.

Bajtazar otrzymuje zlecenia zmiany przychodów postaci $(l, r, \Delta)$ oznaczające konieczność zmiany wszystkich wartości $A[l],\ldots,A[r]$ o $\Delta$ (jeśli $\Delta \ge 0$ — zwiększenie, jeśli $\Delta<0$ — zmniejszenie).

Jeśli w wyniku takiej operacji wartość któregokolwiek pola tablicy $A$ znajdzie się poza zakresem $[0, \ldots, 2\,000\,000\,000]$, to operacja kończy się błędem i Bajtazar odpowiada na takie zlecenie wartością $-1$. W takim wypadku tablica nie jest aktualizowana.

Natomiast jeśli w wyniku takiej operacji wartości tablicy $A$ pozostaną w wymaganym zakresie, tablica jest aktualizowana oraz Bajtazar w odpowiedzi na zlecenie podaje liczbę miesięcy, w których zanotowano wzrost przychodów, tzn:

$$| \{ i : A[i] > A[i-1]\ \mbox{oraz}\ 1 < i \le n \}|.$$

Napisz program, który:

wczyta początkową zawartość tablicy $A$,
wczyta ciąg $m$ operacji zmiany przychodów,
spróbuje sekwencyjnie wykonać każdą operację i wypisze dla każdej z nich jej wynik.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $n$ ($1 \leq n \leq 100\,000$) oznaczająca liczbę miesięcy. W drugim wierszu znajduje się ciąg $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 2\,000\,000\,000$). W trzecim wierszu wejścia znajduje się jedna liczba całkowita $m$ ($1 \leq m \leq 200\,000$) oznaczająca liczbę operacji. W kolejnych $m$ wierszach zapisany jest ciąg operacji. Każdy z tych wierszy zawiera trzy liczby całkowite $l_i, r_i, \Delta_i$ ($1 \le l_i \le r_i \le n$, $-2\,000\,000\,000 \le \Delta_i \le 2\,000\,000\,000$).

Wyjście

W każdym z $m$ wierszy wyjścia należy wypisać jedną liczbę całkowitą — $i$-ty wiersz powinien zawierać wynik $i$-tej operacji.

Przykład

Dla danych wejściowych:
5
1 2 3 4 5
4
1 5 10
2 2 -100
3 4 2000000000
3 4 -12
poprawnym wynikiem jest:
4
-1
-1
3

Archiwum

Poniżej prezentujemy archiwum zadań zaliczeniowych numer 1 z poprzednich edycji laboratorium z ASD.

Zadanie REL (Relaks), r. akad. 2016/2017

Dostępna pamięć: 128MB.

Tomek lubi chodzić po górach, ale jeszcze bardziej lubi odpoczywać podczas wędrówki – może wtedy obserwować przyrodę i robić zdjęcia telefonem. Tomek woli chodzić po swojemu niż korzystać ze szlaków. Znalazł mapę zbocza góry, na którą chce jutro wejść, i dla każdego miejsca ustalił liczbę punktów, które określają, jak bardzo chciałby odpocząć w danym miejscu. Uzyskał w ten sposób tablicę liczb o $ \displaystyle m $ wierszach i $ \displaystyle n $ kolumnach. Tomek zaczyna wędrówkę od odpoczynku w dowolnym polu w dolnym rzędzie; między każdymi dwoma polami odpoczynku przesuwa się o 1 pole w górę i o co najwyżej 2 pola w lewo lub w prawo. Ostatni odpoczynek odbywa się w dowolnym polu w górnym rzędzie, po czym Tomek wchodzi na szczyt, a następnie zaczyna schodzenie w dół od dowolnego innego pola w górnym rzędzie. Schodzenie jest dla niego dużo mniej męczące, dlatego w jednym ruchu przesuwa się o 2 lub 3 pola w dół i co najwyżej 1 w lewo lub w prawo. Ostatni odpoczynek odbywa się w dowolnym polu w dolnym rzędzie, po czym Tomek kończy wędrówkę. Tomek zawsze tak planuje swoją trasę, by nie odpoczywać dwa razy w tym samym polu, bo to nudne (a poza tym nie ma tam nowych Pokemonów). Jaką trasę powinien wybrać, by zdobyć najwięcej punktów?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ \displaystyle m $ oraz $ \displaystyle n $ ( $ \displaystyle 3\le m \le 500 $, $ \displaystyle 2 \le n \le 40 $ ), oznaczające rozmiary tablicy Tomka.

Kolejne $ \displaystyle m $ wierszy zawiera opisy kolejnych rzędów tablicy: $ \displaystyle i $-ty z nich zawiera $ \displaystyle n $ liczb całkowitych $ \displaystyle s_{i,j} $ ( $ \displaystyle 0 \le s_{i,j} \le 100\,000 $ ) oznaczające liczbę punktów, które zdobędzie Tomek za odpoczynek na polu o współrzędnych $ \displaystyle (i,j) $. Wiersze podawane są od najwyższego (najbliższego szczytu) do najniższego.

Wyjście

W pierwszym i jedynym wierszu powinna znaleźć się dokładnie jedna liczba całkowita – największa liczba punktów, którą może osiągnąć Tomek.

Przykład

Dla danych wejściowych:
6 6
9 1 1 1 6 1
1 1 9 1 1 1
1 1 1 8 1 1
1 9 1 6 1 1
1 1 1 9 1 1
1 1 6 9 1 1
poprawnym wynikiem jest:
71

Wyjaśnienie do przykładu:
W optymalnej trasie Tomek będzie wchodził pod górę, odpoczywając po kolei na wszystkich polach wartych po 8 i 9 punktów, a schodził, odpoczywając po kolei na wszystkich polach wartych po 6 punktów (i żadnych innych). Zwróć uwagę, że Tomek nie mógł dwa razy odpoczywać na polu wartym 8 punktów.

Zadanie WYK (Wykopaliska), r. akad. 2014/2015

Dostępna pamięć: 128MB.

W ramach prac archeologicznych profesorowi Makaremu udało się ustalić położenie niezwykle cennych skarbów. Niestety wszystkie one znajdują się bezpośrednio pod obwodnicą otaczającą stolicę Bajtocji. Przypadek? Zapewne nie. Profesor zastanawia się jednak, w jaki sposób dostać się do skarbów.

Udało mu się przekonać inspektorów Bajtockiego Zarządu Dróg, aby przez jedną noc nie zauważyli prac wykopaliskowych, które będzie przeprowadzał. Musi być jednak spełniony jeden warunek - obwodnica ma pozostać przejezdna.

Profesor musi teraz wybrać miejsca, w których będzie prowadził wykopaliska tak, aby zmaksymalizować wartość wykopanych skarbów i jednocześnie nie zatrzymać ruchu na obwodnicy.

Obwodnica ma kształt pierścienia. Ma ona trzy pasy i jest podzielona na $ \displaystyle n $ równych sektorów. Każda para (pas, sektor) wyznacza obszar na obwodnicy, o kształcie podobnym do banana. Jeśli na obwodnicy prowadzone są jakiekolwiek prace, w szczególności prace wykopaliskowe, to zamykane są całe obszary.

Ruch po obwodnicy jest jednokierunkowy, zgodnie ze wskazówkami zegara. Pojazdy mogą jednak zmieniać obszar ruchu na sąsiedni w tym samym sektorze (zmiana pasa) i mogą to robić dowolnie wiele razy w każdym sektorze. Pojazd nie może jechać po zamkniętym obszarze.

Inspektorzy Bajtockiego Zarządu Dróg traktują przejezdność dość elastycznie - wystarczy im, że możliwe jest zrobienie pełnego "kółka" i powrócenie do punktu wyjścia. W szczególności oznacza to, że niektóre niezamknięte obszary obwodnicy mogą być odcięte od reszty.

Profesor dysponuje ograniczoną liczbą ekip i zastanawia się, do których obszarów obwodnicy je wysłać.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle k $ ( $ \displaystyle 1\le k,n \le 5000 $ ), gdzie $ \displaystyle n $ jest liczbą sektorów w obwodnicy, a $ \displaystyle k $ liczbą ekip, które może wysłać profesor. Następne $ \displaystyle n $ wierszy opisuje skarby zgromadzone pod obwodnicą. $ \displaystyle i $-ty z tych wierszy zawiera trzy liczby $ \displaystyle 0 \le v_{i1},v_{i2},v_{i3} \le 5000 $. Są to wartości skarbów zgromadzonych pod $ \displaystyle i $-tym sektorem obwodnicy, każda z liczb opisuje jeden z obszarów
(patrz rysunek).

Wyjście

Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą $ \displaystyle v $ - maksymalną wartość skarbów, jakie może wydobyć profesor, korzystając z nie więcej niż $ \displaystyle k$ ekip.

Przykład
Dla danych wejściowych:
4 4
5 2 1
1 5 2
2 1 5
1 5 2
poprawnym wynikiem jest:
17

Wyjaśnienie do przykładu:
Profesor najchętniej wykopałby cztery skarby, każdy o wartości 5. Niestety wtedy obwodnica przestałaby być przejezdna. Zamiast tego, może on wykopać trzy skarby o wartości 5 i jeden o wartości 2. Rozwiązanie to zostało zaznaczone na rysunku poniżej. Pojazdy mogą wykonywać "kółko" po wewnętrznym pasie.

Natomiast dla danych wejściowych:
4 4
10 10 0
0 0 0
0 10 10
0 0 0
poprawnym wynikiem jest:
40

Zadanie BAJ (Bajtobity), r. akad. 2013/2014

Dostępna pamięć: 64MB.

Przyjazny bajtocki sprzedawca dysponuje pewną liczbą bajtobitów na sprzedaż. Chce je sprzedawać mieszkańcom Bajtocji, biorąc jedną bajtocką monetę za jeden bajtobit. Zgłosiło się do niego kilku mieszkańców, z których każdy dysponuje jakimś budżetem liczonym w bajtockich monetach. Sprzedawca chciałby zadowolić wszystkich kupujących, ale niestety ma mniej bajtobitów niż wynosi suma budżetów. Wie, że kupujący $ \displaystyle A $ będzie niezadowolony wtedy i tylko wtedy, gdy jakiś inny kupujący $ \displaystyle B $ kupi większą liczbę bajtobitów od $ \displaystyle A $ i będzie to liczba, na którą $ \displaystyle A $ stać.

Przykładowo, jeśli pierwszy z kupujących ma budżet 1 i nie kupi ani jednego bajtobitu, a inny kupujący kupi dokładnie jeden bajtobit, to pierwszy kupujący będzie niezadowolony. Natomiast gdyby wszyscy inni kupujący kupili po co najmniej dwa bajtobity, to pierwszy byłby zadowolony. Sprzedawca nie może dzielić bajtobitów, tj. moze sprzedać każdemu klientowi naturalną (z zerem włącznie) liczbę bajtobitów.

Jaką największą liczbę bajtobitów może sprzedać sprzedawca, jeśli chce, żeby nikt nie był niezadowolony?

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1 \leq n \leq 1000 $, $ \displaystyle 1 \leq m < 10\,000 $ ), oznaczające liczbę kupujących i liczbę bajtobitów, którymi dysponuje sprzedawca. W drugim wierszu znajdują się budżety klientów ( $ \displaystyle 1 \leq b_i \leq 1000 $ ), podane w porządku niemalejącym. Suma budżetów jest większa niż $ \displaystyle m $, jednak nie przekracza $ \displaystyle 10\,000 $.

Wyjście

W jedynym wierszu wyjścia należy wypisać maksymalną liczbę bajtobitów, które może sprzedać sprzedawca.

Przykład

Dla danych wejściowych:
5 9
2 2 2 3 3
poprawnym wynikiem jest:
9

Wskazówki

Jaki będzie wynik w przykładzie, gdy liczbę 9 zastąpimy liczbą 11?
Niech $ \displaystyle B $ oznacza sumę budżetów klientów. Postaraj się, aby złożoność czasowa Twojego rozwiązania wynosiła $ \displaystyle O(m B) $.

Zadanie PEN (Pensja), r. akad. 2012/2013

Dostępna pamięć: 32MB.

W związku z kryzysem dyrekcja Bajtockich Zakładów Dezynfekcji Elektrycznych Termoforów zapowiedziała swoim pracownikom cięcia w wynagrodzeniach. Każdy z nich będzie musiał usunąć pewną określoną liczbę cyfr z kwoty swoich miesięcznych dochodów. Pomóż Bajtazarowi napisać program, który pozwoli mu zachować możliwie najwyższą pensję.

Wejście
W pierwszym wierszu znajdują się oddzielone pojedynczymi spacjami dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle k $ ( $ \displaystyle 1 \leq k < n \leq 1\,000\,000 $ ), które oznaczają, odpowiednio, długość zapisu dziesiętnego aktualnej pensji Bajtazara oraz liczbę cyfr do usunięcia.

W drugim wierszu znajduje się liczba $ \displaystyle n $-cyfrowa (bez wiodących zer) oznaczająca aktualną pensję Bajtazara.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać największą liczbę, którą można uzyskać przez usunięcie z aktualnej pensji Bajtazara dokładnie $ \displaystyle k $ cyfr.

Przykład

Dla danych wejściowych:
6 3
768142
poprawnym wynikiem jest:
842

Zadanie TRA (Transport), r. akad. 2011/2012

Dostępna pamięć: 32MB.

Firma przewozowa "Solidnie i nie tak drogo" dowozi do stolicy osoby zamieszkałe w okolicznych wioskach. Każda z osób wsiada do autokaru w swoim miejscu zamieszkania i wysiada w stolicy. Żadne dwie osoby nie wsiadają w tym samym miejscu i wszystkie te miejsca znajdują się na jednej trasie. Opłaty za przejazdy są wnoszone w formie rocznych abonamentów. Firma postanowiła zlecić profesorowi Makaremu wyznaczenie wysokości abonamentów gwarantujących maksymalny zysk. Profesor przeprowadził szereg szczegółowych ankiet, za pomocą których udało mu się oszacować, dla każdej z osób korzystających z usług firmy, maksymalną kwotę, jaką dana osoba jest gotowa zapłacić za abonament - kwotę tę profesor nazwał fachowo "budżetem".

Znając budżety i ceny abonamentów można łatwo przewidzieć zyski firmy. Na osobach, które musiałyby zapłacić za abonament więcej, niż wynosi ich budżet, nie zarabiamy wcale. Na pozostałych osobach zarabiamy dokładnie tyle, ile wynoszą ceny ich abonamentów. Profesor opracował bardzo sprytną metodę pozwalającą wyznaczyć optymalne wysokości abonamentów.

Niestety, algorytm profesora nie bierze pod uwagę ostatnich zmian w przepisach unijnych. Otóż, jeśli trasa A w całości zawiera się w trasie B, to opłata za przejazd trasą A nie może być wyższa niż za przejazd trasą B. Pomóż uratować reputację profesora Makarego i znajdź efektywny algorytm dla tej nieco trudniejszej wersji problemu.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba $ \displaystyle n $ ( $ \displaystyle 1 \le n\le 10\,000 $ ), będąca liczbą przystanków. W drugim wierszu znajduje się $ \displaystyle n $ nieujemnych liczb całkowitych nie większych niż $ \displaystyle 1\,000\,000 $. Liczby te są budżetami kolejnych osób (od osoby mającej do pokonania najwięcej przystanków do osoby, która ze swojego przystanku jedzie bezpośrednio do stolicy).

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać maksymalny zysk, który może osiągnąć firma.

Przykład

Dla danych wejściowych:
4
3 10 5 8
poprawnym wynikiem jest:
20

Zadanie NAW (Nawiasy), r. akad. 2010/2011

Dostępna pamięć: 64MB.

Dana jest dodatnia liczba całkowita $ \displaystyle n $ oraz ciągi rosnące $ \displaystyle { \cal L} $ i $ \displaystyle {\cal R} $ o wartościach ze zbioru $ \displaystyle \{1, 2, \ldots, 2n\} $. Należy określić, ile jest poprawnych wyrażeń nawiasowych długości $ \displaystyle 2n $ takich, że na pozycjach z ciągu $ \displaystyle {\cal L} $ znajdują się nawiasy otwierające, a na pozycjach z ciągu $ \displaystyle {\cal R}$ - zamykające.

Poprawnym wyrażeniem nawiasowym nazywamy napis złożony z nawiasów `[' i `]', zdefiniowany rekurencyjnie:

[] jest poprawnym wyrażeniem nawiasowym;
jeśli $ \displaystyle A $ jest poprawnym wyrażeniem nawiasowym, to [$ \displaystyle A $] również;
jeśli $ \displaystyle A $ i $ \displaystyle B $ są poprawnymi wyrażeniami nawiasowymi, to $ \displaystyle AB $ (sklejenie $ \displaystyle A $ i $ \displaystyle B $ ) również.

Wejście

W pierwszym wierszu znajdują się trzy liczby całkowite $ \displaystyle n $, $ \displaystyle l $ oraz $ \displaystyle r $ ($ \displaystyle 1 \leq n \leq 2000 $, $ \displaystyle 0\leq l, r \leq n $ ), które oznaczają, odpowiednio, liczbę par nawiasów w wyrażeniu, długość ciągu $ \displaystyle {\cal L}$ zadanych pozycji nawiasów otwierających oraz długość ciągu $ \displaystyle {\cal R}$ zadanych pozycji nawiasów zamykających. Drugi wiersz zawiera $ \displaystyle l $ liczb całkowitych $ \displaystyle L_1, L_2, \ldots, L_l$ ( $ \displaystyle 1\leq L_1 < L_2 < \ldots < L_l\leq 2n $ ), stanowiących kolejne wyrazy ciągu $ \displaystyle {\cal L} $. Trzeci wiersz zawiera $ \displaystyle r $ liczb całkowitych $ \displaystyle R_1, R_2, \ldots, R_r $ ( $ \displaystyle 1\leq R_1 < R_2 < \ldots < R_r\leq 2n $), stanowiących kolejne wyrazy ciągu $ \displaystyle {\cal R} $. Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami. Jeśli $ \displaystyle l $ lub $ \displaystyle r $ jest równe 0, to, odpowiednio, drugi lub trzeci wiersz jest pusty.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać resztę z dzielenia przez $ \displaystyle 10^9+7 $ liczby poprawnych wyrażeń nawiasowych długości $ \displaystyle 2n $ z nawiasami otwierającymi na pozycjach z $ \displaystyle {\cal L} $ i zamykającymi na pozycjach z $ \displaystyle {\cal R} $.

Przykład

Dla danych wejściowych:
4 2 1
1 7
3
poprawnym wynikiem jest:
2

Wyjaśnienie do przykładu: Poprawnymi wyrażeniami nawiasowymi spełniającymi podane warunki są [[][]][] oraz [[]][][].

Zadanie PRO (Procenty), r. akad. 2009/2010

Dostępna pamięć: 256MB.

Mieszkający na wsi przyjaciel profesora Makarego od lat zajmuje się badaniem zawartości cukru w cukrze. Ze względu na to, że badania te są ściśle tajne (Chodzi o potwierdzenie procentu cukru w cukrze w zależności od podziemnego promieniowania na danym terenie.), przyjaciel profesora musi być bardzo ostrożny. W szczególności postanowił on nie kupować w tym samym sklepie więcej niż 1 kg cukru dziennie. Aby zmaksymalizować ilość materiału do badań, przyjaciel profesora chciałby odwiedzić każdego dnia wszystkie sklepy we wsi.

Sklepy są usytuowane przy ulicy Sklepowej i otwierane w tym samym momencie, ale zamykane są o różnej porze. Przyjaciel profesora posiada skuter, na którym porusza się pomiędzy sklepami. Przejechanie jednego kilometra zajmuje mu jedną minutę. Czas zakupu cukru w sklepie jest zaniedbywalny. Przyjaciel profesora może rozpocząć zakupy od dowolnego sklepu i chciałby się dowiedzieć, czy możliwe jest odwiedzenie wszystkich sklepów, a jeśli tak, to jaki minimalny czas musi na to poświęcić. Profesor Makary chciałby pomóc swojemu przyjacielowi, ale po zapoznaniu się z wynikami dotychczasowych badań ma z tym problem. Pomóż.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba $ \displaystyle 1 \le n\le 5\,000 $ oznaczająca liczbę sklepów. W każdym z kolejnych $ \displaystyle n $ wierszy znajdują się dwie liczby całkowite $ \displaystyle 0\le d \le 1\,000\,000 $ oraz $ \displaystyle 0 \le t \le 1\,000\,000\,000 $, będące odpowiednio odległością sklepu w kilometrach od północnego końca ulicy Sklepowej i liczbą minut od otwarcia do zamknięcia sklepu.

Wyjście

Twój program powinien wypisać na standardowe wyjście liczbę minut, które przyjaciel profesora musi poświęcić na zakupy, lub słowo "NIE" (bez cudzysłowów), jeśli nie jest możliwe odwiedzenie wszystkich sklepów jednego dnia.

Przykład

Dla danych wejściowych:
5
1 3
3 1
5 6
8 19
10 15
poprawnym wynikiem jest:
11

Wyjaśnienie do przykładu: Przyjaciel profesora może rozpocząć podróż przy sklepie o parametrach $ \displaystyle (3,1) $, a następnie odwiedzać kolejno sklepy: $ \displaystyle (1,3) $, $ \displaystyle (5,6) $, $ \displaystyle (8,19) $ i $ \displaystyle (10,15) $.

Zadanie WIR (Wirówka liczbowa), r. akad. 2008/2009

Dostępna pamięć: 32MB.

Profesor Makary postanowił zbudować odwracającą wirówkę liczbową. Program wirówki działa w następujący sposób.

Do wirówki wsypuje się liczby całkowite.
Jeśli w wirówce pozostała dokładnie jedna liczba, to wirówka kończy pracę.
Wirówka odwirowuje (czyli wyrzuca) największą z liczb, która w niej się znajduje (jeśli takich liczb jest kilka, to wyrzuca tylko jedną).
Wszystkie liczby, które pozostały w wirówce, są odwracane wspak (czyli $ \displaystyle 123 $ staje się $ \displaystyle 321 $, a $ \displaystyle 2020 $ staje się $ \displaystyle 202 $ ).
Wirówka skacze do drugiego kroku programu.

Napisz dla profesora symulator, który będzie przewidywał, jaka liczba pozostanie w wirówce po zakończeniu jej pracy.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1\le n \le 1\,000\,000 $ ), oznaczająca ilość liczb wrzuconych do wirówki. W następych $ \displaystyle n $ wierszach znajdują się kolejne liczby całkowite $ \displaystyle a_i $ ( $ \displaystyle 0\le a_i\le 1\,000\,000\,000 $ ), które zostaną wrzucone do wirówki.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać liczbę, która pozostanie w wirówce po zakończeniu pracy.

Przykład

Dla danych wejściowych:
3
10
21
13
poprawnym wynikiem jest:
1

Załącznik	Wielkość
wykrys-crop.jpg	25.55 KB

Laboratorium 4: drzewo przedziałowe

To laboratorium jest przede wszystkim poświęcone wprowadzeniu bardzo użytecznej w praktyce struktury danych, jaką jest drzewo przedziałowe.

Zadanie KIN ( $ \displaystyle k $-inwersje)

Dostępna pamięć: 64MB.

Niech $ \displaystyle a_1,\ldots,a_n $ będzie permutacją liczb od 1 do $ \displaystyle n $. $ \displaystyle k $-inwersją w tej permutacji nazywamy ciąg indeksów $ \displaystyle i_1,i_2,\ldots,i_k $, taki że $ \displaystyle 1 \le i_1 < i_2 < \ldots < i_k \le n $ oraz $ \displaystyle a_{i_1} > a_{i_2} > \ldots > a_{i_k} $. Twoim zadaniem jest wyznaczenie liczby $ \displaystyle k $-inwersji w zadanej permutacji.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle k $ ( $ \displaystyle 1 \le n \le 20\,000 $, $ \displaystyle 2 \le k \le 10 $ ). Drugi wiersz zawiera permutację liczb $ \displaystyle \{1,\ldots,n\} $.

Wyjście
Twój program powinien wypisać resztę z dzielenia przez $ \displaystyle 10^9 $ z liczby $ \displaystyle k $-inwersji w podanej permutacji.

Przykład

Dla danych wejściowych:
4 3
4 3 1 2
poprawnym wynikiem jest:
2

Wskazówki dla studentów

Na początku zaproponuj rozwiązanie tego zadania w złożoności czasowej $ \displaystyle O(n^2 k) $. W tym celu zastosuj programowanie dynamiczne.
Zastanów się, jak usprawnić poprzednie rozwiązanie, tak by działało w czasie $ \displaystyle O(nk\log n) $, stosując statyczne drzewo przedziałowe (można o nim poczytać np. tutaj).
Jaką złożoność pamięciową ma Twoje rozwiązanie?

Laboratorium 5: drzew przedziałowych ciąg dalszy

Zadanie MAL (Malowanie autostrady)

Dostępna pamięć: 128MB.

Profesor Makary, chcąc pomóc rządowi Bajtocji, maluje nieodpłatnie autostradę. Autostrada ma długość $ \displaystyle n $ kilometrów i jest podzielona na kilometrowe odcinki ponumerowane $ \displaystyle 1,\ldots,n $. Profesor ma do dyspozycji białą farbę.

Początkowo cała autostrada jest czarna. Profesor Makary nocą, jeśli męczy go bezsenność, wychodzi na autostradę z kubełkiem farby i maluje pewien odcinek autostrady. Niestety niekiedy w autostradzie pojawiają się dziury i wtedy w dzień przyjeżdża walec i kładzie asfalt. Poasfaltowany fragment drogi staje się oczywiście czarny. Profesor chciałby mieć na bieżąco dostęp do informacji o tym, ile kilometrów autostrady jest pomalowanych białym kolorem. Pomóż profesorowi w tym odpowiedzialnym zadaniu.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1\le n \le 1\,000\,000 $ ), oznaczająca długość autostrady. W drugim wierszu znajduje się liczba całkowita $ \displaystyle m $ ( $ \displaystyle 1\le m \le 1\,000\,000 $ ), oznaczająca sumę liczb nocy malowań i dni walcowań. W każdym z następych $ \displaystyle m $ wierszy znajdują się dwie liczby całkowite $ \displaystyle 1\le a \le b \le n $ i litera $ \displaystyle c $. Liczby $ \displaystyle a,b $ są końcami malowanego odcinka, $ \displaystyle c $ opisuje zdarzenie. B oznacza, że profesor malował autostradę, a C oznacza, że jeździł po niej walec.

Wyjście
Po wczytaniu każdego z wierszy, Twój program powinien wypisać na wyjście liczbę kilometrów pomalowanych kolorem białym.

Przykład

Dla danych wejściowych:
12
4
1 5 C
2 10 B
4 6 B
4 7 C
poprawnym wynikiem jest:
0
9
9
5

Laboratorium 6: ciąg dalszy struktur danych

Jest to ostatnie z grupy laboratoriów poświęconych strukturom danych. Tym razem zadanie dotyczy drzew binarnych. Uwaga: Jest to nieco inne zadanie niż przed rokiem.

Zadanie PAR (Park Bitowy)

Dostępna pamięć: 128MB.

W Parku Bitowym znajduje się $ \displaystyle n $ polanek ponumerowanych od 1 do $ \displaystyle n $. Niektóre pary polanek są połączone (dwukierunkowymi) ścieżkami. Jak to przystało na park bitowy, układ ścieżek tworzy drzewo binarne, którego korzeniem jest polanka numer 1.

Bajtek i Bajtyna przyszli po szkole pobawić się w parku. Dzieci postanowiły zagrać w następującą grę. Naprzemiennie jedno z dzieci wskazuje numer polanki $ \displaystyle a $ oraz liczbą całkowitą nieujemną $ \displaystyle d $, a zadaniem drugiego z nich jest odnalezienie w parku jakiejś polanki, której odległość
od polanki $ \displaystyle a $ wynosi $ \displaystyle d $. Jeśli takiej polanki nie ma, dziecko musi to określić.

Bajtek chciałby sobie ułatwić grę. Poprosił Cię, żebyś napisał program, który będzie odnajdował polanki określone przez Bajtynę.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 500\,000 $ ), oznaczająca liczbę polanek w Parku Bitowym. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera dwie liczby całkowite $ \displaystyle a_i $ oraz $ \displaystyle b_i $ ( $ \displaystyle a_i,b_i \in \{-1,1,2,\ldots,n\} $ ), oznaczające, że z polanki numer $ \displaystyle i $ prowadzą ścieżki na polanki numer $ \displaystyle a_i $ oraz $ \displaystyle b_i $. Wartość $ \displaystyle -1 $ oznacza, że dana ścieżka nie istnieje. Dane wejściowe zawierają wszystkie krawędzie konieczne do jednoznacznego zbudowania drzewa ukorzenionego w polance numer 1.

W kolejnym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle m $ ( $ \displaystyle 1 \le m \le 500\,000 $ ), oznaczająca liczbę poleceń, które Bajtek otrzymał od Bajtyny. Każdy z następnych $ \displaystyle m $ wierszy zawiera dwie liczby całkowite $ \displaystyle a $ oraz $ \displaystyle d $ ( $ \displaystyle 1 \le a\le n $, $ \displaystyle 0 \le d < n $ ).

Wyjście

Twój program powinien wypisać numery polanek stanowiące odpowiedzi na pytania Bajtyny. Jeśli odpowiedzią na dane pytanie jest więcej niż jedna polanka, Twój program powinien wypisać jakąkolwiek z nich. Jeśli polanka wskazana przez Bajtynę nie istnieje, w odpowiednim wierszu należy wypisać liczbę $ \displaystyle -1 $.

Przykład

Dla danych wejściowych:
8
3 4
-1 6
2 5
-1 -1
7 -1
-1 -1
8 -1
-1 -1
6
1 3
1 4
1 5
6 1
6 4
6 5
poprawnym wynikiem jest:
6
8
-1
2
4
8

Wskazówki dla studentów

Pokaż, jak dla każdego wierzchołka $ \displaystyle u $ i dla każdego całkowitego $ \displaystyle 0 \le i \le \log n $ wyznaczyć wierzchołek położony $ \displaystyle 2^i $ krawędzi ponad wierzchołkiem $ \displaystyle u $.
Sprowadź całe zadanie do następującego: dla danych dwóch wierzchołków $ \displaystyle u $ i $ \displaystyle v $, znajdź wierzchołek położony na ścieżce między tymi wierzchołkami, którego odległość od $ \displaystyle u $ wynosi $ \displaystyle d_u $, a odległość od $ \displaystyle v $ wynosi $ \displaystyle d_v $. W sprowadzeniu może Ci być potrzebne proste programowanie dynamiczne na drzewie.
Rozwiązanie wzorcowe ma złożoność czasową i pamięciową $ \displaystyle O(n\log n) $.

Zadanie zaliczeniowe 2

Do tego zadania nie będzie wskazówek. To drugie, ostatnie zadanie zaliczeniowe. Należy je rozwiązywać samodzielnie, a po rozwiązaniu uzyskać akceptację laboranta.

Zadanie PRZ (Przedziały), r. akad. 2014/2015

Dostępna pamięć: 128MB.

Dany jest zbiór liczb całkowitych $ \displaystyle S=\{1,2,\ldots,n\} $. Dla $ \displaystyle a $ i $ \displaystyle b $ całkowitych, $ \displaystyle a\le b $, przedziałem $ \displaystyle [a,b] $ nazywamy zbiór kolejnych liczb całkowitych od $ \displaystyle a $ do $ \displaystyle b $: $ \displaystyle \{a, a + 1, \ldots, b\} $. Częściowym rozbiciem zbioru $ \displaystyle S $ na przedziały nazywamy taki ciąg parami rozłącznych przedziałów, że suma tych przedziałów zawiera się w $ \displaystyle S $.

Twoim zadaniem jest napisać losowy generator częściowych rozbić zbioru $ \displaystyle S $ na przedziały. Generator będzie działał w sposób iteracyjny. W danym momencie pamiętamy zbiór liczb całkowitych, które są w $ \displaystyle S $, a nie zostały użyte jeszcze w żadnym przedziale. Zaczynamy od całego zbioru $ \displaystyle S $. Następnie w każdej iteracji losujemy jakiś przedział i usuwamy go ze zbioru. Postępujemy tak $ \displaystyle m $ razy, gdzie $ \displaystyle m $ to moc częściowego rozbicia, którą chcemy uzyskać.

Losowanie przedziału należy wykonać jak następuje. Mamy pewien podzbiór zbioru $ \displaystyle S $. Oznaczmy go przez $ \displaystyle T $. Wylosowany przedział musi się zawierać w $ \displaystyle T $. Numerujemy wszystkie przedziały, które się zawierają w $ \displaystyle T $, od zera w kolejności leksykograficznej względem początku i końca przedziału. Np. dla $ \displaystyle T=\{1, 4, 5\} $ kolejne przedziały to: $ \displaystyle [1, 1], [4, 4], [4, 5], [5, 5] $ i mają one odpowiednio numery $ \displaystyle 0, 1, 2, 3 $. Wyboru przedziału dokonujemy przez wylosowanie numerka. Numerek losuje sprawdzaczka.

Wejście i wyjście
Twój program powinien działać według następującego schematu. Najpierw należy wczytać jedną liczbę całkowitą $ \displaystyle n $ ( $ 1\le n\le 2\,000\,000\,000 $ ). Następnie należy zainicjować $ \displaystyle T=\{1,2,\ldots,n\} $ oraz wypisać liczbę $ \displaystyle L $ oznaczającą, ile jest przedziałów zawartych w $ \displaystyle T $. Teraz należy wykonać pewną liczbę iteracji, nie większą jednak niż $ \displaystyle 1\,000\,000 $. W pojedynczej iteracji należy:

wczytać ze standardowego wejścia liczbę całkowitą $ \displaystyle l $ ( $ \displaystyle -1 <= l < L $ ), oznaczającą numerek wygenerowanego przedziału, chyba że $ \displaystyle l=-1 $, wtedy należy zakończyć działanie programu,
wypisać dwie liczby całkowite $ \displaystyle a $ i $ \displaystyle b $ oddzielone pojedynczym odstępem oznaczające wybrany przedział $ \displaystyle [a, b] $,
usunąć wszystkie elementy przedziału $ \displaystyle [a, b] $ ze zbioru $ \displaystyle T $,
wypisać na standardowe wyjście liczbę przedziałów $ \displaystyle L $ zawierających się w $ \displaystyle T $.

Przykład
Dla danych wejściowych:
5
6
2
0
-1
poprawnym wynikiem jest:
15
2 3
4
4 5
1
1 1
0

Archiwum

Poniżej umieszczamy archiwum zadań zaliczeniowych numer 2 z poprzednich edycji laboratorium z ASD.

Zadanie OBC (Obciążenie drogi), r. akad. 2013/2014

Dostępna pamięć: 128MB.

W związku z organizowanymi Ogólnoświatowymi Ważnymi Ekonomicznie Zawodami przeprowadzony został bajtocki program Rozwoju Dróg. Do każdej miejscowości w Bajtocji jest teraz doprowadzona autostrada! Niestety, z powodu braku funduszy, wszystkie skrzyżowania autostrad znajdują się w miejscowościach. Na dodatek między dowolnymi dwiema miejscowościami istnieje tylko jedna trasa, być może przebiegająca przez jakieś miejscowości pośrednie. Autostrady są rzecz jasna dwukierunkowe.

Teraz czas zająć się utrzymaniem dróg. W związku z tym przygotowywana jest Lista Inwestycji Priorytetowych (Autostrady). Trzeba tylko, w celu przeprowadzenia badania zużycia nawierzchni, wyznaczyć najbardziej obciążony odcinek autostrady, czyli taki odcinek, po którym jeździ najwięcej pojazdów.

Profesor Makary podjął się tego trudnego i odpowiedzialnego zadania. Szczęśliwie Nadzór Użytkowania Dróg i Autostrad zainstalował we wszystkich pojazdach lokalizatory i przygotował listę podróży z ostatniego tygodnia.

Pomóż prof. Makaremu wyznaczyć liczbę pojazdów, które przejechały najbardziej obciążonym odcinkiem autostrady.

Przykład

Dla danych wejściowych:
6 3
1 2
3 2
4 3
3 5
0 2
0 1 2
5 4 2
1 3 3
poprawnym wynikiem jest:
5

Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle m $ ( $ \displaystyle 2 \le n \le 500\,000 $, $ \displaystyle 1 \le m \le 500\,000 $ ) oznaczające odpowiednio liczbę miast i opisów przejazdów.

Miasta numerowane są od $ \displaystyle 0 $ do $ \displaystyle n-1 $. W kolejnych $ \displaystyle n-1 $ wierszach znajdują się pary liczb oznaczające numery miast bezpośrednio połączonych odcinkiem autostrady.

W dalszych $ \displaystyle m $ wierszach podane są trójki liczb: $ \displaystyle a, b, k $ ( $ \displaystyle 0 \le a \ne b < n $, $ \displaystyle 1 \le k \le 100\,000\,000 $ ), oznaczające, że trasą pomiędzy miastami $ \displaystyle a $ i $ \displaystyle b $ przejechało $ \displaystyle k $ pojazdów. Nie ma tras o początku i końcu w tym samym mieście. Trasy na wejściu mogą się powtarzać.

Wyjście
Jedyny wiersz wyjścia powinien zawierać liczbę samochodów, które przejechały najbardziej obciążonym odcinkiem.

Przykład

Dla danych wejściowych:
6 3
1 2
3 2
4 3
3 5
0 2
0 1 2
5 4 2
1 3 3
poprawnym wynikiem jest:
5

Zadanie PRD (Prodziekan do spraw studenckich), r. akad. 2012/2013

Dostępna pamięć: 64MB.

Prodziekan do spraw studenckich westchnął i posmutniał. Było wcześnie rano, a przed jego gabinetem już stała kolejka $ \displaystyle n $ studentów. Dyżur dziekana rozpoczyna się zawsze w południe. Za kilka godzin zapowiadał się więc długi i żmudny dyżur.

Dziekan wie, że nie jest w stanie przyjąć więcej niż $n$ studentów w ciągu jednego dyżuru. Aby jednak dać szansę studentom, którzy przyjdą później, ale przed rozpoczęciem dyżuru, a przykładają się do nauki, zarządził następującą zasadę. Jeśli kolejny student przyjdzie z zamiarem ustawienia się w kolejce, nie może on ustawić się na końcu kolejki (gdyż wtedy miałaby ona już $ \displaystyle n+1 $ osób), lecz zamiast tego może wejść do kolejki w miejsce drugiej w kolejności osoby, która ma średnią niższą od niego. Jeśli taka osoba nie istnieje, student nie może ustawić się w kolejce. Osoba usunięta z kolejki odchodzi i nie będzie mogła dziś spotkać się z dziekanem (nawet jeśli mogłaby się ponownie ustawić w kolejce na powyższych zasadach).

Wiedząc, którzy studenci stoją obecnie w kolejce i którzy studenci będą próbowali się w niej ustawić przed początkiem dyżuru, wyznacz, komu i w jakiej kolejności uda się dziś odwiedzić dziekana. Dziekan przyjmie wszystkie $ \displaystyle n $ osób stojących w kolejce przed początkiem dyżuru.

Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle m $ ( $ \displaystyle 1 \leq n,m \leq 200\,000 $ ) oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę studentów stojących w kolejce rano i liczbę studentów, którzy próbują ustawić się w kolejce w ciągu dnia. Wszyscy studenci ponumerowani są liczbami całkowitymi z przedziału $ \displaystyle [1,n+m] $ wg średnich; student o numerze $ \displaystyle i $ ma większą średnią niż student o numerze $ \displaystyle j $ wtedy i tylko wtedy, gdy $ \displaystyle i > j $, a żadnych dwóch studentów nie ma równych średnich.

W drugim wierszu wejścia znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle a_i $ ( $ \displaystyle 1 \leq a_i \leq n+m $ dla $ \displaystyle 1 \leq i \leq n $ ), pooddzielanych pojedynczymi odstępami, oznaczających numery studentów stojących w porannej kolejce do prodziekana, w porządku, w jakim stoją w kolejce. W trzecim wierszu wejścia znajduje się $ \displaystyle m $ liczb całkowitych $ \displaystyle b_j $ ( $ \displaystyle 1 \leq b_j \leq n+m $ dla $ \displaystyle 1 \leq j \leq m $ ), pooddzielanych pojedynczymi odstępami, oznaczających numery studentów próbujących ustawić się w kolejce do początku dyżuru, w kolejności, w jakiej przychodzą. Możesz założyć, że wszystkie liczby $ \displaystyle a_i $ oraz $ \displaystyle b_j $ są parami różne.

Wyjście
W pierwszym i jedynym wierszu wyjścia Twój program powinien wypisać $ \displaystyle n $ parami różnych liczb, pooddzielanych pojedynczymi odstępami, oznaczających numery kolejnych studentów, którzy będą stać w kolejce do prodziekana w chwili rozpoczęcia dyżuru, w kolejności przyjmowania ich przez prodziekana.

Przykład

Dla danych wejściowych:
5 5
6 8 5 1 3
7 2 10 4 9
poprawnym wynikiem jest:
6 10 9 1 4

Wyjaśnienie do przykładu:

Student 7 ma wyższą średnią od wszystkich studentów stojących w kolejce, poza studentem 8, stojącym na drugiej pozycji; wyrzuca on zatem z kolejki studenta 5 (który jest drugim w kolejności studentem o średniej niższej niż student 7) i wchodzi na jego miejsce. Po przyjściu studenta 7 kolejka ma więc postać 6, 8, 7, 1, 3.
Student 2 ma średnią wyższą tylko od studenta 1, i nie ma kogo wyrzucić z kolejki. Po przyjściu tego studenta kolejka dalej ma postać 6, 8, 7, 1, 3.
Student 10 ma najwyższą średnią, i, zgodnie z zasadami, zastępuje studenta 8. Po przyjściu studenta 10 kolejka ma więc postać 6, 10, 7, 1, 3.
Student 4 ma średnią wyższą od studentów 1 i 3 i zastępuje studenta 3. Po przyjściu studenta 4 kolejka ma więc postać 6, 10, 7, 1, 4.
Od studenta 9 tylko student 10 ma wyższą średnią, więc student 9 zastępuje studenta 7. Tuż przed rozpoczęciem dyżuru kolejka ma więc postać 6, 10, 9, 1, 4.

Zadanie RDZ (Rdza), r. akad. 2011/2012

Dostępna pamięć: 32MB.

Profesor Makary prowadzi badania nad wpływem kwaśnych deszczów na stan torowisk tramwajowych w klimacie umiarkowanym. Zaplanowany przez profesora eksperyment polega na upuszczaniu w ściśle określonych momentach kropli stężonego kwasu na szynę tramwajową i obserwowaniu rozszerzających się po szynie plam rdzy. Ognisko rdzy na szynie zainicjowane przez spadającą kroplę kwasu rozszerza się w tempie 1mm/sek w obydwu kierunkach aż do końca szyny. Profesor chciałby obliczyć, kiedy cała szyna zostanie pokryta rdzą. Pomóż mu!

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite $ \displaystyle d $ i $ \displaystyle n $ ( $ \displaystyle 1 \leq d\leq 10^9 $, $ \displaystyle 1\leq n \leq 100\,000$ ), które oznaczają, odpowiednio, długość szyny w milimetrach oraz liczbę kropel kwasu upuszczonych na szynę. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera dwie liczby całkowite $ \displaystyle x $ i $ \displaystyle t $, gdzie $ \displaystyle 0\le x\le d $, $ \displaystyle 0\le t\le 10^9 $, opisujące miejsce i czas upuszczenia kropli kwasu. Liczba $ \displaystyle x $ oznacza odległość kropli w milimetrach od lewego końca szyny, a liczba $ \displaystyle t $ - moment upuszczenia kropli na szynę, mierzony w sekundach licząc od początku eksperymentu.

Wyjście

W jedynym wierszu wyjścia należy wypisać najmniejszą całkowitą liczbę sekund od początku eksperymentu do momentu, w którym cała szyna będzie pokryta rdzą.

Przykład

Dla danych wejściowych:
10 4
2 0
8 1
5 1
7 4
poprawnym wynikiem jest:
3

Wyjaśnienie do przykładu. Po pierwszej sekundzie eksperymentu rdzą będzie pokryty fragment od 1 do 3 milimetra szyny, po drugiej fragment od początku szyny do 6 milimetra i od 7 do 9 milimetra.

Zadanie CIA (Ciasta), r. akad. 2010/2011

Dostępna pamięć: 64MB.

Znajomi profesora Makarego - Krzysiek, Marcin i kilku innych - odkryli ostatnio nowe hobby, a mianowicie pieczenie ciast. Zrodziło to niezbyt zdrową konkurencję - któreś z ciast musi być przecież najlepsze. Profesor Makary ma dokonać oceny.

Wyróżnił on trzy cechy, które są najistotniejsze dla smaku: czekoladowość, słodkość i owocowość. Każdą z tych cech daje się jednoznacznie ocenić w skali od $ \displaystyle 0 $ do $ \displaystyle 10^9 $. Udało mu się też ustalić, że jeśli mamy ciasto $ \displaystyle A $, które jest mniej czekoladowe, mniej słodkie i mniej owocowe niż ciasto $ \displaystyle B $, to ciasto $ \displaystyle B $ na pewno będzie lepsze, czyli przy wyborze najlepszego ciasta, ciasto $ \displaystyle A $ można pominąć.

Pomóż profesorowi ustalić, ilu ciast musi minimalnie spróbować, aby wybrać najlepsze. Zakładamy (naturalnie), że profesor tak czy siak pragnie spróbować co najmniej jednego ciasta.

Wejście

W pierwszym wierszu znajduje się liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \leq n \leq 50\,000$ ), oznaczająca liczbę ciast. W każdym z kolejnych $ \displaystyle n $ wierszy znajdują się trzy liczby całkowite z zakresu $ \displaystyle 0 \ldotp\ldotp 10^9 $ oznaczające, odpowiednio, czekoladowość, słodkość i owocowość danego ciasta. Są one oddzielone pojedynczymi odstępami. Nie ma dwóch ciast o takiej samej czekoladowości, ani dwóch o takiej samej słodkości, ani dwóch o takiej samej owocowości.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać minimalną liczbę ciast, których należy spróbować, aby wybrać najlepsze.

Przykład

Dla danych wejściowych:
3
1 1 1
6 2 2
5 3 3
poprawnym wynikiem jest:
2

Zadanie CIE (Cięciwy), r. akad. 2009/2010

Dostępna pamięć: 128MB.

Na okręgu danych jest $ \displaystyle n $ cięciw, z których żadne dwie nie mają wspólnego końca i żadne trzy nie przecinają się w jednym punkcie. Każda z cięciw jest pomalowana na jeden spośród $ \displaystyle k $ kolorów. Znajdź łączną liczbę punktów przecięcia par cięciw różnych kolorów.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle k $ ( $ \displaystyle 1 \leq n, k \leq 100\,000 $ ) oddzielone pojedynczym odstępem i oznaczające, odpowiednio, liczbę cięciw i liczbę dostępnych kolorów. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera trzy liczby całkowite $ \displaystyle a $, $ \displaystyle b $, $ \displaystyle c $, przy czym $ \displaystyle 1\le a, b\le 2n $, $ \displaystyle 1\le c\le k $. Liczby $ \displaystyle a $ i $ \displaystyle b $ są numerami punktów stanowiących końce cięciwy (wszystkie końce cięciw są ponumerowane od $ \displaystyle 1 $ do $ \displaystyle 2n $ w kolejności ich występowania na okręgu), a liczba $ \displaystyle c $ oznacza jej kolor. Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać liczbę przecięć par cięciw różnych kolorów.

Przykład

Dla danych wejściowych:
4 3
1 7 1
2 5 3
3 6 1
4 8 1
poprawnym wynikiem jest:
2

Zadanie MAL (Malowanie autostrady), r. akad. 2008/2009

Dostępna pamięć: 128MB.

Wejście

Wyjście
Po wczytaniu każdego z wierszy, Twój program powinien wypisać na wyjście liczbę kilometrów pomalowanych kolorem białym.

Przykład

Dla danych wejściowych:
12
4
1 5 C
2 10 B
4 6 B
4 7 C
poprawnym wynikiem jest:
0
9
9
5

Laboratorium 7: zastosowanie biblioteki STL

Zadanie z tego laboratorium stanowi pretekst do przypomnienia i rozszerzenia wiadomości o bibliotece STL, w szczególności pokazania, w jaki sposób można wykorzystywać jej kontenery i metody do pisania efektywnych programów (efektywnych z algorytmicznego punktu widzenia). Bardzo wygodna jest, na przykład, reprezentacja grafu rzadkiego w tablicy vectorów bądź list (realizacja list sąsiedztwa).

Zadanie PRJ (Projekty)

Dostępna pamięć: 256MB.

Bajtazar właśnie awansował na szefa działu informatyki Bardzo Ważnej Instytucji Państwowej. W jego obowiązkach jest zarządzanie projektami informatycznymi. Instytucja przygotowała listę potencjalnych projektów, które powinny zostać wykonane. Niestety wykonanie niektórych projektów zależy od pomyślnego wykonania innych. Dodatkowo, każdy projekt charakteryzuje się minimalną liczbą programistów, którzy są konieczni do jego wykonania.

Ze względu na cięcia budżetowe nie jest możliwe wykonanie wszystkich projektów. Zarząd zdecydował, że zrealizowane zostanie jedynie $ \displaystyle k $ projektów. Bajtazar dostał polecenie zatrudnienia minimalnej liczby programistów, którzy są konieczni do zrealizowania co najmniej $ \displaystyle k $ projektów (przy czym projekty mogą być realizowane sekwencyjnie, tak że programiści są przenoszeni z jednego projektu do drugiego).

Napisz program, który pomoże Bajtazarowi i wyznaczy minimalną liczbę programistów, których należy zatrudnić.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczba całkowite $ \displaystyle n $, $ \displaystyle m $ i $ \displaystyle k $ ( $ \displaystyle 1 \leq n \leq 100\,000 $, $ \displaystyle 0 \leq m \leq 500\,000 $, $ \displaystyle 0 \le k \le n $ ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę projektów, liczbę zależności pomiędzy projektami oraz minimalną liczbę projektów, które należy zrealizować. W kolejnych $ \displaystyle n $ wierszach zostały zapisane informacje o liczbie programistów koniecznych do wykonania projektów. W $ \displaystyle (i+1) $-szym wierszu została zapisana liczba całkowita $ \displaystyle p_i $ ( $ \displaystyle 1\le p_i \le 100\,000\,000 $ ) oznaczająca, że do wykonania $ \displaystyle i $-tego projektu konieczne jest zatrudnienie $ \displaystyle p_i $ programistów. W kolejnych $ \displaystyle m $ wierszach zostały zapisane informacje o zależnościach pomiędzy projektami. Każdy z tych wierszy zawiera dwie liczby całkowite $ \displaystyle a $, $ \displaystyle b $ ( $ \displaystyle 1\le a,b \le n $, $ \displaystyle a\ne b $ ) oddzielone pojedynczym odstępem i oznaczające, że do wykonania projektu $ \displaystyle a $ konieczne jest ukończenie projektu $ \displaystyle b $.

Możesz założyć, że zależności pomiędzy projektami nie tworzą cykli.

Wyjście

W jedynym wierszu standardowego wyjścia należy wypisać minimalną liczbę programistów, których należy zatrudnić, tak by było możliwe wykonanie $ \displaystyle k $ projektów.

Przykład

Dla danych wejściowych:
5 3 3
10
500
150
200
100
1 2
1 3
4 5
poprawnym wynikiem jest:
200

Wskazówki dla studentów

Jak rozwiązałbyś to zadanie (tzn. wyznaczył listę projektów, które należy zrealizować), gdyby do wykonania każdego projektu wystarczałby jeden programista? (tj. wszystkie $ \displaystyle p_i=1 $ )
W poprzednim podpunkcie możliwe są dwa liniowe rozwiązania. Pokaż, jak zmodyfikować to z nich, które opiera się na odpowiedniej strukturze danych, aby rozwiązać powyższe zadanie w pełnej ogólności. Wykorzystaj stosowny kontener z biblioteki STL.

Laboratorium 8: biblioteki STL ciąg dalszy i jeden ważny a klasyczny algorytm

Na tym laboratorium kontynuujemy prezentację zastosowań biblioteki STL do implementacji efektywnych algorytmów, tak się akurat składa, że nadal grafowych. Tym razem na tapecie algorytm Dijkstry.

Zadanie KAP (Kapitan)

Dostępna pamięć: 256MB.

Kapitan Bajtazar przemierza wody Morza Bajtockiego wraz ze swoim niezastąpionym pierwszym oficerem Bajtkiem. Na morzu znajduje się $ \displaystyle n $ wysp, które numerujemy liczbami od 1 do $ \displaystyle n $. Przy wyspie numer 1 przycumował statek kapitana. W ramach wyprawy kapitan planuje popłynąć na wyspę numer $ \displaystyle n $.

W trakcie rejsu statek zawsze porusza się w jednym z czterech kierunków świata: na północ, południe, wschód lub zachód. W każdym momencie przy sterach stoi albo kapitan, albo pierwszy oficer. Za każdym razem, gdy statek wykona skręt o $ \displaystyle 90^\circ $, zmieniają się oni przy sterach.

Po drodze statek może zatrzymywać się przy innych wyspach. Po każdym postoju kapitan może zdecydować, czy obejmuje stery jako pierwszy. Innymi słowy, na każdym fragmencie trasy prowadzącym z wyspy do wyspy jeden z marynarzy obejmuje stery, gdy statek płynie na północ lub południe, a drugi z nich steruje podczas rejsu na wschód lub zachód. W szczególności, jeśli pewien fragment trasy prowadzi dokładnie w jednym z czterech kierunków świata, na tym fragmencie steruje tylko jeden z marynarzy.

Kapitan zastanawia się teraz, jak zaplanować trasę najbliższego rejsu i podział pracy, by spędzić jak najmniej czasu przy sterze. Jednocześnie kapitan nie przejmuje się, jak długa będzie wyznaczona trasa. Przyjmujemy, że statek płynie ze stałą prędkością jednej jednostki na godzinę.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 200\,000 $ ) oznaczającą liczbę wysp na morzu. Dla uproszczenia na Morze Bajtockie nanosimy układ współrzędnych, którego osie są równoległe do kierunków świata. Każdą z wysp reprezentujemy jako pojedynczy punkt. Kolejne $ \displaystyle n $ wierszy zawiera opisy wysp: $ \displaystyle i $-ty z nich zawiera dwie liczby całkowite $ \displaystyle x_i $, $ \displaystyle y_i $ ( $ \displaystyle 0 \le x_i,y_i \le 1\,000\,000\,000 $ ) oznaczające współrzędne $ \displaystyle i $-tej wyspy na morzu. Każda wyspa ma inne współrzędne.

Wyjście

Twój program powinien wypisać na wyjście jedną liczbę całkowitą, oznaczającą najmniejszą liczbę godzin, przez które kapitan będzie musiał sterować statkiem na trasie z wyspy numer 1 do wyspy numer $ \displaystyle n $.

Przykład

Dla danych wejściowych:
5
2 2
1 1
4 5
7 1
6 7
poprawnym wynikiem jest:
2

Wyjaśnienie do przykładu: Kapitan może wyznaczyć trasę, którą zaznaczono na obrazku. W trakcie rejsu z wyspy 1 (współrzędne (2, 2)) na wyspę 4 (współrzędne (7, 1)) kapitan steruje tylko przez godzinę, gdy statek płynie na południe. W trakcie drugiego fragmentu podróży kapitan steruje jedynie wtedy, gdy statek porusza się na wschód.

Wskazówki dla studentów

Użyj algorytmu Dijkstry w odpowiednim grafie (zauważ, że nie może on być zbyt duży).

Załącznik	Wielkość
kaprys-crop.gif	10.82 KB

Laboratorium 9: odrobina algorytmów tekstowych

Po serii zagadnień grafowych, na zakończenie cyklu zadań "normalnych" z laboratorium z ASD pojawia się zadanie ze stringologii. Podczas laboratorium prezentujemy dwa różne rozwiązania tego zadania, jedno bardziej teoretyczne i w praktyce mniej efektywne (oparte na metodzie etykietowania), a drugie efektywniejsze, choć obarczone teoretyczną niepewnością wyniku (korzystające z haszowania).

Zadanie LEX (Porównywanie leksykograficzne)

Dostępna pamięć: 64MB.

Niech $ \displaystyle s=s_1s_2\ldots s_n $ będzie $ \displaystyle n $-literowym słowem złożonym z małych liter alfabetu angielskiego. Będziemy zajmować się podsłowami tego słowa, czyli spójnymi fragmentami postaci $ \displaystyle s[i{\ldotp\ldotp}j]=s_is_{i+1}\ldots s_j $. Naszym celem jest leksykograficzne porównywanie różnych par takich podsłów.

Powiemy, że słowo $ \displaystyle u $ jest mniejsze leksykograficznie (czyli słownikowo) niż słowo $ \displaystyle v $, jeżeli:

słowo $ \displaystyle u $ jest prefiksem właściwym słowa $ \displaystyle v $, tzn. $ \displaystyle u $ stanowi początkowy fragment $ \displaystyle v $ krótszy niż $ \displaystyle v $, lub
słowa $ \displaystyle u $ i $ \displaystyle v $ różnią się na jakiejś pozycji i na pierwszej takiej różniącej je pozycji $ \displaystyle u $ zawiera literę mniejszą niż odpowiadająca jej litera w słowie $ \displaystyle v $.

Tę relację zapisujemy jako $ \displaystyle u < v $.

Na przykład, słowo abaab jest (leksykograficznie) mniejsze niż abaababa, słowo abaa jest mniejsze niż ababa, ale ani abab nie jest mniejsze niż abaab, ani słowo abaab nie jest mniejsze od abaab (czyli od siebie samego).

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1 \le n,m \le 300\,000 $ ), oznaczające długość słowa $ \displaystyle s $ oraz liczbę zapytań. Drugi wiersz zawiera $ \displaystyle n $-literowe słowo. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera cztery liczby całkowite $ \displaystyle a,b,c,d $ ( $ \displaystyle 1 \le a \le b \le n $, $ \displaystyle 1 \le c \le d \le n $ ), oznaczające zapytanie o porównanie leksykograficzne słów $ \displaystyle s[a{\ldotp\ldotp}b] $ oraz $ \displaystyle s[c{\ldotp\ldotp}d] $.

Wyjście

Na standardowe wyjście Twój program powinien wypisać $ \displaystyle m $ wierszy, z których każdy powinien zawierać jeden znak: '<', '>' lub '=', w zależności od tego, czy pierwsze podsłowo z danego zapytania jest mniejsze czy większe leksykograficznie od drugiego podsłowa, czy też równe temu podsłowu.

Przykład

Dla danych wejściowych:
13 3
abaababaabaab
8 13 7 7
6 11 4 6
3 5 11 13
poprawnym wynikiem jest:
<
>
=

Wyjaśnienie do przykładu: W pierwszym zapytaniu rozważamy podsłowa aabaab oraz b, w drugim - abaaba oraz aba, a w trzecim - aab oraz aab.

Wskazówki dla studentów

Metoda I: chcemy przydzielać podsłowom słowa identyfikatory liczbowe, tak aby porównywanie identyfikatorów podsłów tej samej długości odpowiadało porównaniu leksykograficznemu. Jak przydzielić takie etykiety wszystkim podsłowom o długościach będących potęgami dwójki? (w czasie $ \displaystyle O(n\log{n}) $ ) Jak porównywać podsłowa innych długości, korzystając z tych identyfikatorów? (w czasie $ \displaystyle O(1) $ )
Metoda II: tutaj podsłowom będziemy chcieli przydzielać hasze, o tej własności, że równość haszy z dużym prawdopodobieństwem implikuje równość podsłów. Haszem dla podsłowa $ \displaystyle s[i \ldotp\ldotp j] $ będzie $ \displaystyle (s_i+p \cdot s_{i+1}+p^2 \cdot s_{i+2}+\ldots+p^{j-i}s_j) \bmod q $. Jak dobrać wartości parametrów $ \displaystyle p $ i $ \displaystyle q $? Jakie wstępne obliczenia wykonać, aby móc obliczać takie hasze dla podsłów w czasie stałym? Jak porównywać leksykograficznie podsłowa, korzystając z takich haszy? (czas $ \displaystyle O(\log{n}) $ )

Laboratorium 10: Find & Union

Poniższe zadanie można rozwiązać w zadowalający sposób na kilka różnych sposobów. W tym laboratorium proponujemy rozwiązanie używające struktury danych dla zbiorów rozłącznych, ale i nie tylko.

Zadanie INW (Graf inwersji)

Dostępna pamięć: 128MB.

Bajtazar odkrył nową rodzinę grafów nieskierowanych, które można reprezentować za pomocą inwersji. Niech $ \displaystyle V = \{1,2,\ldots,n\} $ będzie zbiorem wierzchołków grafu, natomiast $ \displaystyle a_1,a_2,\ldots,a_n $ - pewnym ciągiem parami różnych liczb ze zbioru $ \displaystyle V $. Wierzchołki $ \displaystyle a_i $ oraz $ \displaystyle a_j $ są połączone krawędzią w grafie, jeśli para $ \displaystyle (i,j) $ jest inwersją w tym ciągu, to znaczy $ \displaystyle i < j $ oraz $ \displaystyle a_i > a_j $.

Dla przykładu rozważmy $ \displaystyle n=4 $ i ciąg 2, 3, 1, 4. Wtedy uzyskujemy graf jak na rysunku:

Bajtazar chce pokazać, że wymyślona przez niego reprezentacja jest użyteczna. Postanowił napisać program, który wyznacza spójne składowe grafu. Przypomnijmy, że dwa wierzchołki $ \displaystyle u,v\in V $ znajdują się w tej samej spójnej składowej grafu, jeśli istnieje taki ciąg wierzchołków, którego pierwszym wyrazem jest $ \displaystyle u $, ostatnim - $ \displaystyle v $, a każde dwa kolejne wierzchołki są połączone krawędzią grafu. W naszym przykładzie mamy dwie spójne składowe: $ \displaystyle \{1,2,3\} $ oraz $ \displaystyle \{4\} $.

Pomóż Bajtazarowi!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \leq n \leq 1\,000\,000 $ ) oznaczająca liczbę wierzchołków grafu. W drugim wierszu znajduje się ciąg $ \displaystyle n $ liczb całkowitych $ \displaystyle a_1, a_2, \ldots, a_n $.

Wyjście

W pierwszym wierszu wyjścia należy wypisać liczbę spójnych składowych grafu; oznaczmy tę liczbę przez $ \displaystyle m $. W każdym z kolejnych $ \displaystyle m $ wierszy należy podać opis jednej spójnej składowej grafu. Na początku wiersza wypisać należy liczbę $ \displaystyle k $ oznaczającą rozmiar składowej, a następnie rosnący ciąg $ \displaystyle k $ numerów wierzchołków tej składowej. Składowe należy wypisać w takiej kolejności, by pierwsze numery wierzchołków z każdego wiersza tworzyły ciąg rosnący. Innymi słowy, jeśli $ \displaystyle S $ i $ \displaystyle S' $ są dwiema składowymi, $ \displaystyle u \in S $, $ \displaystyle v\in S' $ są ich najmniejszymi wierzchołkami oraz \( \displaystyle uPrzykład

Dla danych wejściowych:
4
2 3 1 4
poprawnym wynikiem jest:
2
3 1 2 3
1 4

Wskazówki dla studentów

Zadanie karne

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?

Jeśli rozwiązałem co najmniej jedno zadanie rozgrzewkowe (z dwóch z pierwszego laboratorium), oba zadania zaliczeniowe (i uzyskałem akceptację swoich rozwiązań u laboranta) oraz sześć zadań zwykłych (z puli ośmiu), a chciałbym zaliczyć laboratorium z ASD w I terminie. Wówczas oprócz zadania karnego muszę rozwiązać jeszcze co najmniej jedno brakujące zadanie zwykłe.
Jeśli chciałbym zaliczyć laboratorium w II terminie. Wówczas oprócz zadania karnego muszę uzupełnić wszystkie braki w laboratorium, czyli rozwiązać najpóźniej na tydzień przed rozpoczęciem egzaminu poprawkowego: 1 zadanie rozgrzewkowe, 7 zadań zwykłych i 2 zadania zaliczeniowe (rozwiązania zadań zaliczeniowych muszą uzyskać akceptację laboranta).
Jeśli nie spełniam żadnego z powyższych kryteriów, a lubię rozwiązywać zadania algorytmiczne, chcę rozwijać swoje umiejętności algorytmiczno-programistyczne i/lub poćwiczyć przed egzaminem praktycznym z ASD.

Zadanie ULA (Ula), r. akad. 2014/2015

Dostępna pamięć: 128MB.

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

Archiwum

Zadanie PPL (Podpalindrom), r. akad. 2013/2014

Dostępna pamięć: 32MB.

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

Zadanie ROB (Roboty), r. akad. 2012/2013

Dostępna pamięć: 256MB.

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:

Robot $ \displaystyle Y $ przesuwa się na pozycję 3.
Robot $ \displaystyle X $ przesuwa się na pozycję 1.
Robot $ \displaystyle Y $ przesuwa się na pozycję 4.
Robot $ \displaystyle X $ przesuwa się na pozycję 2.

Zadanie KUR (Kurort), r. akad. 2011/2012

Dostępna pamięć: 128MB.

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

Zadanie SLO (Słowa), r. akad. 2010/2011

Dostępna pamięć: 64MB.

Pojedynczą zmianą w słowie nazwiemy:

usunięcie litery (np. $ \displaystyle \mathtt{ABCD} \to \mathtt{ACD} $ )
wstawienie litery (np. $ \displaystyle \mathtt{ABCD} \to \mathtt{ABECD} $ )
zamianę litery na inną (np. $ \displaystyle \mathtt{ABCD} \to \mathtt{AECD} $ ).

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} $.

Zadanie PRF (Profesor), r. akad. 2009/2010

Dostępna pamięć: 32MB.

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ł:

Każda reakcja powoduje przekształcenie substancji w inną. Reakcję przekształcającą substancję $ \displaystyle S_1 $ w $ \displaystyle S_2 $ będziemy oznaczali $ \displaystyle S_1 \rightarrow S_2 $. Może istnieć więcej niż jedna reakcja postaci $ \displaystyle S_1 \rightarrow S_2 $.
Istnienie reakcji przekształcającej $ \displaystyle S_1 $ w $ \displaystyle S_2 $ (w skrócie $ \displaystyle S_1 \rightarrow S_2 $ ) nie gwarantuje istnienia reakcji odwrotnej ( $ \displaystyle S_2 \rightarrow S_1 $ ).
Są jednak pewne specjalne reakcje, nazwijmy je reakcjami odwracającymi. Wykonanie takiej reakcji powoduje, że odtąd wszystkie reakcje (włącznie z tą właśnie wykonaną) zmieniają kierunek: jeśli przed wykonaniem reakcji odwracającej mamy do dyspozycji reakcję $ \displaystyle S_1 \rightarrow S_2 $, to po jej wykonaniu potrafimy wykonać $ \displaystyle S_2 \rightarrow S_1 $. Po kolejnym wykonaniu (dowolnej) reakcji odwracającej wracamy do sytuacji pierwotnej.

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.

Zadanie DOM (Domino), r. akad. 2008/2009

Dostępna pamięć: 32MB.

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

Trening przed egzaminem

Tym razem proponujemy trening na zadaniach z ubiegłorocznych egzaminów praktycznych. Wcześniej jednak - przypomnienie zasad zaliczania dotyczących egzaminu poprawkowego praktycznego.

Aby przystąpić do egzaminu poprawkowego laboratoryjnego, należy zaliczyć laboratorium, w I lub w II terminie. Podczas egzaminu każdy student pracuje na swoim koncie i może korzystać z dostępnych zasobów elektronicznych (dowolne manuale, zrobione przez siebie zadania) oraz z przyniesionych ze sobą notatek i książek. Kontaktowanie się z innymi osobami będzie karane dwóją z egzaminu. Do rozwiązania będą co najmniej dwa zadania w czasie 3 godzin. Żeby zaliczyć egzamin, wystarczy rozwiązać w pełni jedno zadanie (zaliczane automatycznie przez SIO); za każde następne rozwiązane zadanie uzyskuje się pół oceny więcej od tej wynikającej z wyników egzaminu pisemnego. Osoby, które nie zaliczą części praktycznej, nie będą dopuszczone do części pisemnej egzaminu.

Archiwum

Poniżej treści zadań z poprzednich egzaminów praktycznych. Rozwiązania wzorcowe tych zadań można znaleźć w załącznikach.

Zadanie NAS (Naszyjniki), r. akad. 2015/2016, I termin, zadanie prostsze

Dostępna pamięć: 64MB.

Bajtockie naszyjniki składają się z wielu elementów o różnych kolorach. Ceną danego naszyjnika jest długość jego najdłuższego spójnego fragmentu o tym samym kolorze elementów -- (np. naszyjnik 1 2 1 1 3 1 ma cenę 2).

Bajtazar otrzymał $ \displaystyle n $ niezbyt cennych naszyjników (z których każdy składa się z $ \displaystyle \ell $ elementów) i chciałby z nich otrzymać dokładnie jeden naszyjnik o maksymalnej cenie. Otrzymany naszyjnik również powinien składać sie z $ \displaystyle \ell $ elementów.

Niestety reguły produkcji naszyjników są dosyć restrykcyjne. Jeśli jakiś element naszyjnika był choć raz wykorzystany na $ \displaystyle i $-tej pozycji, to nigdy już nie może wystąpić na innej pozycji.

Czyli zgodnie z regułami w otrzymanym naszyjniku na $ \displaystyle i $-tej pozycji ( $ \displaystyle 1\le i \le \ell $ ) można wykorzystać dokładnie jeden z $ \displaystyle i $-tych elementów wejściowych naszyjników.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowitą $ \displaystyle n $ i $ \displaystyle \ell $ ( $ \displaystyle 1 \le n \le 100\,000 $, $ \displaystyle 1 \le \ell \le 200\,000 $ ), oznaczającą liczbę naszyjników oraz ich długość. Można założyć, że $ \displaystyle n\cdot \ell \le 2\cdot 10^6 $. Kolejne $ \displaystyle n $ wierszy zawiera opisy naszyjników: $ \displaystyle j $-ty z nich zawiera $ \displaystyle \ell $ liczb całkowitych $ \displaystyle s_i $ ( $ \displaystyle 0 \le s_i \le 1\,000\,000\,000 $ ) oznaczające kolory kolejnych elementów $ \displaystyle j $-tego naszyjnika.

Wyjście
Twój program powinien wypisać na wyjście jedną liczbę całkowitą, oznaczającą maksymalną cenę naszyjnika, który możemy otrzymać.

Przykład
Dla danych wejściowych:
3 4
1 2 1 2
1 1 3 3
3 1 3 2
poprawnym wynikiem jest:
3

Wyjaśnienie do przykładu:
Dla przykładowych naszyjników możemy otrzymać naszyjnik 1 1 1 2 o cenie 3 (pierwszy element pochodzi z naszyjnika numer 1, drugi z naszyjnika numer 2, trzeci element z naszyjnika numer 1 i 4 element z naszyjnika numer 3).

Zadanie TRA (Trasa), r. akad. 2015/2016, I termin, zadanie trudniejsze

Dostępna pamięć: 64MB.

W zadaniu rozważamy silnie spójne grafy skierowane, w których wagi krawędzi zmieniają się w czasie. Dla zadanych wierzchołków $ \displaystyle a $ i $ \displaystyle b $ należy obliczyć najtańszą trasę rozpoczynającą się w wierzchołku $ \displaystyle a $ przechodzącą przez wierzchołek $ \displaystyle b $ i wracającą do $ \displaystyle a $.

Każda krawędź grafu $ \displaystyle e=(u,v) $ ma pewną ustaloną wagę początkową $ \displaystyle c_e $, która następnie ulega zmianie w kolejnych jednostkach czasu o $ \displaystyle p_e $ (jeśli $ \displaystyle p_e>0 $ waga wzrasta, jeśli $ \displaystyle p_e<0 $ waga maleje).

W zadaniu rozważamy graf w jednostkach czasu $ \displaystyle t\in \{1,\ldots,d\} $, można też założyć, że dla zadanych danych wejściowych wartości $ \displaystyle w_e $ i $ \displaystyle p_e $ są tak dobrane, że waga zawsze będzie dodatnia.

Napisz program, który:

wczyta opis grafu $ \displaystyle G $, numery wierzchołków $ \displaystyle a $ i $ \displaystyle b $ oraz maksymalną wartość czasu $ \displaystyle d $,
wyznaczy minimalny koszt trasy z $ \displaystyle a $ do $ \displaystyle b $ i z powrotem, przy założeniu, że możemy wybrać dowolny czas $ \displaystyle t\in \{1,\ldots,d\} $,
wypisze obliczony koszt.

Wejście
W pierwszym wierszu wejścia znajduje się pięć liczb całkowitych $ \displaystyle n, m, a, b, d $, $ \displaystyle 2\le n \le 100\,000 $, $ \displaystyle 1\le m \le 100\,000 $, $ \displaystyle 2\le d \le 10\,000 $, gdzie $ \displaystyle n $ jest liczbą wierzchołków grafu, $ \displaystyle m $ liczbą krawędzi, $ \displaystyle a $ numerem wierzchołka startowego, $ \displaystyle b $ numerem wierzchołka końcowego ( $ \displaystyle a\not=b $ ), $ \displaystyle d $ maksymalnym rozważanym czasem. Wierzchołki są numerowane 1 do $ \displaystyle n $. W następnych $ \displaystyle m $ wierszach znajdują się opisy kolejnych krawędzi. Każdy wiersz zawiera sześć liczb całkowitych: $ \displaystyle n_1, n_2, c_1, p_1, c_2, p_2 $. Liczby $ \displaystyle n_1 $ i $ \displaystyle n_2 $ to numery wierzchołków, które łączy krawędź. Liczby $ \displaystyle c_1 $ i $ \displaystyle c_2 $ oznaczają początkowe wagi krawędzi $ \displaystyle n_1 $ do $ \displaystyle n_2 $ oraz z $ \displaystyle n_2 $ do $ \displaystyle n_1 $. W każdej kolejnej jednostce czasu waga pierwszej krawędzi zmienia się o $ \displaystyle p_1 $, a waga drugiej krawędzi o $ \displaystyle p_2 $. Wiadomo, że dla $$ \displaystyle t=\{1,\ldots,d\} $ każda waga będzie dodatnia i nigdy nie przekroczy $ \displaystyle 10\,000 $.

Wyjście
W pierwszym i jedynym wierszu powinna się znajdować dokładnie jedna liczba całkowita --- minimalny koszt trasy z $ \displaystyle a $ do $ \displaystyle b $ i z powrotem.

Przykład
Dla danych wejściowych:
4 4 1 4 3
1 2 5 -1 10 -1
3 2 12 2 7 2
3 4 8 -1 20 -3
1 4 27 -2 3 0
poprawnym wynikiem jest:
23

Patrz rysunek: http://smurf.mimuw.edu.pl/sites/default/files/trazad.jpg

Jednym z optymalnych rozwiązań dla testu przykładowego jest trasa $ \displaystyle 1 \to 2 \to 3 \to 4 \to 1 $ dla $ \displaystyle t=2 $, kiedy to koszt trasy wynosi 23.

Zadanie EST (Estetyczne ciągi), r. akad. 2015/2016, II termin, zadanie prostsze

Dostępna pamięć: 128MB.

W Bajtocji ciąg liczbowy $ \displaystyle a_1,\ldots,a_k $ jest uważany za estetyczny, jeśli każde dwa kolejne elementy ciągu różnią się co najwyżej o 1:

$ \displaystyle |a_{i+1} - a_i| \le 1\ \mbox{dla}\ 1 \le i < k $

Na przykład ciąg $ \displaystyle 1,1,2,1,0,0 $ jest estetyczny, natomiast $ \displaystyle 1,3,4,3 $ nie jest estetyczny.

Bajtazar otrzymał ciąg składający się z $ \displaystyle n $ liczb: $ \displaystyle s_1,\ldots,s_n $, chciałby z niego otrzymać jak najdłuższy ciąg estetyczny. Może wybrać dowolne elementy wejściowego ciągu i dowolnie zmieniać ich kolejność.

Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle n $ ( $ \displaystyle 1 \le n \le 100\,000 $ ), oznaczającą długość wejściowego ciągu. Kolejne $ \displaystyle n $ wierszy zawiera opis ciągu: $ \displaystyle i $-ty z nich zawiera jedną liczbę całkowitą $ \displaystyle s_i $ ( $ \displaystyle 0 \le s_i \le 1\,000\,000\,000 $ ) oznaczające kolejne elementy wejściowego ciągu.

Wyjście
Twój program powinien wypisać na wyjście jedną liczbę całkowitą, oznaczającą maksymalną długość estetycznego ciągu, który można otrzymać z $ \displaystyle s_1,\ldots,s_n $.

Przykład
Dla danych wejściowych:
7
1
6
2
5
7
6
10
poprawnym wynikiem jest:
4

Wyjaśnienie do przykładu: Dla przykładowego ciągu możemy otrzymać estetyczny ciąg długości 4: 6 5 6 7.

Zadanie POT (Potworzyca), r. akad. 2015/2016, II termin, zadanie trudniejsze

Dostępna pamięć: 512MB.

Potworzyca porusza się po platformach umieszczonych nad przepaścią. Przepaść jest podzielona na $ \displaystyle X \times Y $ kwadratów, nad kwadratem o współrzędnych $ \displaystyle (i,j) $ ( $ \displaystyle 1 \leq i \leq X, 1 \leq j \leq Y $ ) znajduje się jedna platforma, na wysokości $ \displaystyle h_{i,j} $ cm. Jeśli Potworzyca znajduje się na platformie nad kwadratem $ \displaystyle (i,j) $, to może ona w ciągu 1 sekundy się przemieścić na platformę nad polem $ \displaystyle (i',j') $, o ile $ \displaystyle |i-i'| \leq 2 $, $ \displaystyle |j-j'| \leq 2 $, i $ \displaystyle |h_{i,j} - h_{i',j'}| \leq H $, gdzie $ \displaystyle H $ to skoczność Potworzycy. Może ona również w ciągu jednej sekundy przesunąć platformę, na której się znajduje, o 1 cm w górę lub dół. Potworzyca znajduje się na platformie nad $ \displaystyle (1,1) $. Ile czasu potrzebuje, by dostać się do Męża Potwora na platformę nad polem $ \displaystyle (X,Y) $?

Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite $ \displaystyle X $, $ \displaystyle Y $, i $ \displaystyle H $ ( $ \displaystyle 1 \le X,Y \le 500 $, $ \displaystyle 0 \le H \le 1\,000\,000 $ ), oznaczającą wymiary przepaści oraz skoczność Potworzycy. Kolejne $ \displaystyle X $ wierszy zawiera opisy platform: $ \displaystyle i $-ty z nich zawiera $ \displaystyle Y $ liczb całkowitych $ \displaystyle h_{i,1}, \ldots, h_{i,Y} $ oznaczających kolejne wysokości platform, gdzie $ \displaystyle 0 \leq h_{i,j} \leq 1\,000\,000 $.

Wyjście
Twój program powinien wypisać na wyjście jedną liczbę całkowitą, oznaczającą ilość czasu potrzebnego Potworzycy na dotarcie na platformę nad pole $ \displaystyle (X,Y) $ (w sekundach).

Przykład
Dla danych wejściowych:
7 9 25
100 360 110 370 120 380 130 390 140
340 350 900 900 900 280 270 260 150
330 999 900 900 120 900 900 900 400
320 440 180 430 290 420 160 410 250
450 999 999 999 170 999 999 999 240
190 310 999 300 999 999 999 999 230
999 460 200 470 210 480 220 490 520
poprawnym wynikiem jest:
39

Zadanie PAR (Parking), r. akad. 2014/2015, I termin, zadanie prostsze

Dostępna pamięć: 128MB.

Bajtazar pracuje przy obsłudze parkingu w głównej siedzibie firmy ByteSoft. Projektant parkingu, profesor Bajtoni, na co dzień zajmuje się algorytmami grafowymi.

Opis parkingu.
Parking składa się z miejsc parkingowych, ponumerowanych od 1 do $ \displaystyle n $. Między niektórymi parami miejsc występują dwukierunkowe połączenia. Między każdą parą miejsc jest co najwyżej jedno takie połączenie. Na każdym miejscu parkingowym może znajdować się co najwyżej jeden samochód. Główną wadą projektową parkingu jest to, że jeśli dane miejsce parkingowe jest zajęte, żaden samochód nie może przez nie przejechać. Szczęśliwie, jeśli na parkingu nie ma żadnych samochodów, to jest możliwe przejechanie z dowolnego miejsca parkingowego na dowolne inne miejsce parkingowe (innymi słowy mówiąc, graf miejsc parkingowych jest spójny).

Przy miejscu parkingowym numer 1 znajduje się wyjazd z parkingu. Na niektórych miejscach parkingowych są zaparkowane samochody. Pomóż Bajtazarowi stwierdzić, dla każdego samochodu, czy może on wyjechać z parkingu tym wyjazdem. Możesz założyć, że miejsce parkingowe numer 1 jest wolne.

Drugi wiersz wejścia zawiera ciąg bitów $ \displaystyle b_1,\ldots,b_n $, pooddzielanych pojedynczymi odstępami. Bit $ \displaystyle b_i $ oznacza, czy na miejscu parkingowym numer $ \displaystyle i $ znajduje się jakiś samochód (bit 1), czy też nie (bit 0). Możesz założyć, że $ \displaystyle b_1=0 $ oraz że co najmniej jeden bit w ciągu jest równy 1.

Każdy z kolejnych $ \displaystyle m $ wierszy zawiera dwie liczby całkowite $ \displaystyle u_j $ oraz $ \displaystyle v_j $ ( $ \displaystyle 1 \le u_j,v_j \le n $, $ \displaystyle u_j \ne v_j $ ), oznaczające połączenie biegnące między miejscami parkingowymi $ \displaystyle u_j $ i $ \displaystyle v_j $.

Wyjście
Twój program powinien wypisać na wyjście numery wszystkich miejsc parkingowych, na których są zaparkowane samochody, z których każdy (niezależnie) mógłby opuścić parking wyjazdem znajdującym się przy miejscu parkingowym numer 1. Liczby należy wypisać w osobnych wierszach, w kolejności rosnącej.

Przykład
Dla danych wejściowych:
6 7
0 0 1 1 1 0
1 2
2 3
2 4
1 4
4 5
5 6
6 4
poprawnym wynikiem jest:
3
4

Patrz rysunek: http://smurf.mimuw.edu.pl/sites/default/files/parrys-crop.jpg

Zadanie PAD (Parking 2), r. akad. 2014/2015, I termin, zadanie trudniejsze

Dostępna pamięć: 128MB.

Bajtazar pracuje przy obsłudze parkingu w głównej siedzibie firmy ByteSoft. Jest to ten sam parking, który występuje w treści zadania prostszego -- szczegóły można znaleźć w sekcji Opis parkingu.

Przy niektórych miejscach parkingowych znajdują się wyjazdy z parkingu. Samochód może wyjechać danym wyjazdem, tylko jeśli na drodze od jego miejsca parkingowego do wyjazdu nie jest zaparkowany żaden inny samochód (a zatem także i miejsce parkingowe, przy którym znajduje się wyjazd, musi być puste).

Każdego dnia po południu do Bajtazara zgłaszają się kolejni pracownicy firmy, pytając, czy mogą swoimi samochodami wyjechać z parkingu przez wybrane przez siebie wyjazdy. Jeśli Bajtazar odpowiada pracownikowi twierdząco, pracownik wyjeżdża z parkingu -- tak więc nie ma go już na parkingu, gdy zadawane są kolejne zapytania pracowników. Pomóż Bajtazarowi w udzielaniu odpowiedzi na pytania pracowników.

Drugi wiersz wejścia zawiera ciąg bitów $ \displaystyle b_1,\ldots,b_n $, pooddzielanych pojedynczymi odstępami. Bit $ \displaystyle b_i $ oznacza, czy na miejscu parkingowym numer $ \displaystyle i $ znajduje się jakiś samochód (bit 1), czy też nie (bit 0). Możesz założyć, że co najmniej jeden bit w ciągu jest równy 1. W przeciwieństwie do zadania prostszego, nie występuje tu dodatkowe założenie, że $ \displaystyle b_1=0 $.

Każdy z kolejnych $ \displaystyle m $ wierszy zawiera dwie liczby całkowite $ \displaystyle u_j $ oraz $ \displaystyle v_j $ ( $ \displaystyle 1 \le u_j,v_j \le n $, $ \displaystyle u_j \ne v_j $), oznaczające połączenie biegnące między miejscami parkingowymi $ \displaystyle u_j $ i $ \displaystyle v_j $.

Kolejny wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle q $ ( $ \displaystyle 1 \le q \le 500\,000 $ ), oznaczającą liczbę zapytań. Każdy z kolejnych $ \displaystyle q $ wierszy zawiera dwie liczby całkowite $ \displaystyle m_k $, $ \displaystyle w_k $ ( $ \displaystyle 1 \le m_k,w_k \le n $, $ \displaystyle m_k \ne w_k $ ) oznaczające zapytanie pracownika parkującego na miejscu $ \displaystyle m_k $, który pyta o możliwość opuszczenia parkingu z użyciem wyjazdu znajdującego się przy miejscu parkingowym numer $ \displaystyle w_k $. Możesz założyć, że przy takim zapytaniu rzeczywiście zachodzi $ \displaystyle b_{m_k}=1 $.

Wyjście
Twój program powinien wypisać na wyjście $ \displaystyle q $ wierszy z odpowiedziami Bajtazara, z których każda to TAK lub NIE.

Przykład
Dla danych wejściowych:
6 7
0 0 1 1 1 0
1 2
2 3
2 4
1 4
4 5
5 6
6 4
6
3 6
5 1
3 1
4 5
4 6
5 1
poprawnym wynikiem jest:
NIE
NIE
TAK
NIE
TAK
TAK

Zadanie WZN (Wzniesienia), r. akad. 2014/2015, II termin, zadanie prostsze

Dostępna pamięć: 128MB.

W tym zadaniu mamy dany graf nieskierowany z całkowitymi dodatnimi wagami na krawędziach. Wzniesieniem w grafie nazywamy ścieżkę prostą złożoną z dwóch krawędzi, z których druga ma większą wagę niż pierwsza. Napisz program, który zliczy wzniesienia w podanym grafie.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 2 \le n \le 500\,000 $, $ \displaystyle 1 \le m \le 500\,000 $ ) oznaczające liczbę wierzchołków i liczbę krawędzi w grafie. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera trzy liczby całkowite $ \displaystyle u_i $, $ \displaystyle v_i $, $ \displaystyle w_i $ ( $ \displaystyle 1 \le u_i,v_i \le n $, $ \displaystyle 1 \le w_i \le 1\,000\,000 $ ), opisujące nieskierowaną krawędź: jej końce i jej wagę. Możesz założyć, że graf nie zawiera pętli ani krawędzi wielokrotnych.

Wyjście
Twój program powinien wypisać na wyjście jeden wiersz zawierający jedną liczbę całkowitą: liczbę wzniesień w grafie.

Przykład
Dla danych wejściowych:
5 6
1 2 1
2 3 2
3 4 3
4 1 4
1 5 2
5 2 1
poprawnym wynikiem jest:
8

natomiast dla danych wejściowych:
7 6
1 2 1
1 3 1
1 4 2
1 5 2
1 6 3
1 7 3
poprawnym wynikiem jest:
12

Zadanie AUT (Autostrada), r. akad. 2014/2015, II termin, zadanie trudniejsze

Dostępna pamięć: 128MB.

Bajtazar zarządza jednokierunkową dwupasmową autostradą z Bajtyża do Bajtawy. Każdy z dwóch pasów ruchu złożony jest z $ \displaystyle n $ kwadratowych płyt, jak na rysunku http://smurf.mimuw.edu.pl/sites/default/files/autrys1-crop.jpg

Niestety, autostrada często jest blokowana przez demonstracje bitników. Każda grupa protestujących bitników zajmuje jeden odcinek dzielący dwie płyty autostrady, co powoduje, że samochód nie może przejechać przez ten odcinek. Bajtazar przez cały dzień dostaje informacje o pojawieniu się lub zniknięciu grupy protestujących i musi na bieżąco odpowiadać na zapytania, czy autostrada jest przejezdna, czy nie. Pomóż mu!

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 2 \le n \le 500\,000$, $ \displaystyle 1 \le m \le 500\,000 $ ) oznaczające długość autostrady i liczbę zdarzeń. Na początku między każdymi dwiema sąsiednimi płytami da się przejechać.

Każdy z kolejnych $ \displaystyle m $ wierszy zawiera parę liczb $ \displaystyle i $ oraz $ \displaystyle t $ ( $ \displaystyle 0 \le i \le n-1 $, $ \displaystyle 0 \le t \le 2 $ ) określającą zmianę przejezdności między dwiema płytami autostrady. Wartość $ \displaystyle t=0 $ oznacza, że zmiana dotyczy odcinka między punktami $ \displaystyle (i,1) $ i $ \displaystyle (i+1,1) $, $ \displaystyle t=1 $ oznacza, że zmiana dotyczy odcinka między $ \displaystyle (i,0) $ a $ \displaystyle (i,1) $, a $ \displaystyle t=2 $ oznacza, że zmiana dotyczy odcinka między $ \displaystyle (i,1) $ a $ \displaystyle (i,2) $. (Układ współrzędnych według rysunku powyżej.) Każda para liczb oznacza zmianę stanu odcinka przez nią reprezentowanego: jeśli przed zmianą przez odcinek dało się przejechać, to po zmianie się nie da, a jeśli nie dało się przejechać, to po zmianie się da.

Wyjście
Twój program powinien wypisać na wyjście $ \displaystyle m $ wierszy z odpowiedziami Bajtazara, z których każda to TAK lub NIE -- odpowiedź oznacza, czy po kolejnej zmianie przejezdności da się przejechać całą autostradą.

Przykład
Dla danych wejściowych:
10 6
2 0
4 0
2 1
5 2
3 0
4 0
poprawnym wynikiem jest:
TAK
TAK
TAK
TAK
NIE
TAK

Poniższy rysunek przedstawia sytuację na autostradzie po wszystkich zmianach: http://smurf.mimuw.edu.pl/sites/default/files/autrys2-crop.jpg

Zadanie SKI (Skierowanie), r. akad. 2013/2014, I termin, zadanie prostsze

Dostępna pamięć: 256MB.

Dany jest pewien graf nieskierowany. Czy można skierować krawędzie tego grafu tak, by w wynikowym grafie skierowanym nie istniała ścieżka (skierowana) złożona z więcej niż jednej krawędzi?

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 2 \le n \le 500\,000 $, $ \displaystyle 1 \le m \le 500\,000 $ ), oznaczające liczbę wierzchołków i liczbę krawędzi w grafie. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera dwie liczby całkowite $ \displaystyle a_i $, $ \displaystyle b_i $ ( $ \displaystyle 1\le a_i,b_i \le n $, $ \displaystyle a_i \ne b_i $ ), oznaczające krawędź grafu. W grafie nie ma pętli ani krawędzi wielokrotnych.

Wyjście
Twój program powinien wypisać jeden wiersz zawierający jedno słowo TAK lub NIE, w zależności od tego, czy istnieje żądane skierowanie krawędzi grafu.

Przykład
Dla danych wejściowych:
5 6
1 2
2 3
3 4
4 1
1 5
5 3
poprawnym wynikiem jest:
TAK

natomiast dla danych wejściowych:
5 4
1 2
2 3
3 1
4 5
poprawnym wynikiem jest:
NIE

Zadanie PRE (Prelegenci), r. akad. 2013/2014, I termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Uniwersytet Bajtocki organizuje dwudniowy cykl wykładów pt. Bit i bajt. Komitet programowy cyklu chciałby na każdy z dni zaprosić wybitnego specjalistę w dziedzinie informatyki teoretycznej, aby wygłosił tego dnia wykład plenarny. Członkowie komitetu stworzyli listę $n$ wybitnych naukowców, spośród których chcieliby wybrać dwóch prelegentów. Decyzja, których dwóch prelegentów zaprosić, ma swój aspekt finansowy.

Każdy z prelegentów wyznaczył pewną kwotę, którą mu trzeba zapłacić, aby zgodził się wygłosić jeden z wykładów plenarnych. Ponadto niektórzy prelegenci nie lubią się wzajemnie. Jeśli chcieć zaprosić na wykłady dwóch nielubiących się prelegentów, trzeba każdemu z nich zapłacić pewną dodatkową kwotę jako rekompensatę za pracę w trudnych warunkach. Komitet programowy poprosił Cię, abyś pomógł mu wybrać dwóch prelegentów, których zaproszenie jest najbardziej ekonomiczne (czyli, mówiąc wprost, będzie kosztować najmniej pieniędzy).

Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 500\,000 $ ), oznaczającą liczbę prelegentów. W drugim wierszu znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle a_1,\ldots,a_n $ ( $ \displaystyle 1 \le a_i \le 100\,000\,000 $ ); liczba $ \displaystyle a_i $ reprezentuje koszt zaproszenia $ \displaystyle i $-tego prelegenta. W trzecim wierszu znajduje się jedna liczba całkowita $ \displaystyle m $ ( $ \displaystyle 1 \le m \le 500\,000 $ ), oznaczająca liczbę par prelegentów, którzy się nie lubią. W kolejnych $ \displaystyle m $ wierszach znajdują się opisy tych par. Każdy taki opis składa się z trzech liczb całkowitych $ \displaystyle u_i $, $ \displaystyle v_i $, $ \displaystyle b_i $ ( $ \displaystyle 1 \le u_i,v_i \le n $, $ \displaystyle u_i \ne v_i $, $ \displaystyle 1 \le b_i \le 100\,000\,000 $ ), które oznaczają, że prelegenci $ \displaystyle u_i $ i $ \displaystyle v_i $ nie lubią się i jeśli obu ich zaprosić na wykłady, trzeba każdemu z nich zapłacić $ \displaystyle b_i $. Pary $ \displaystyle \{u_i, v_i\} $ nie mogą się powtarzać.

Wyjście
Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą minimalny koszt zorganizowania wykładów z udziałem dwóch różnych prelegentów.

Przykład
Dla danych wejściowych:
4
3 2 4 8
4
1 2 5
1 3 1
3 2 2
1 4 1
poprawnym wynikiem jest:
9

Wyjaśnienie do przykładu: Komitet programowy powinien zaprosić pierwszego i trzeciego prelegenta, którzy nie lubią się "tylko trochę'".

Zadanie ZET (Żetony I), r. akad. 2013/2014, II termin, zadanie prostsze

Dostępna pamięć: 256MB.

Uwaga: Zadanie prostsze (Żetony I, ZET) różni się od trudniejszego (Żetony II, ZED) jedynie ograniczeniem na $ \displaystyle m_i $.

Jaś ma pewną liczbę jednakowych żetonów, które poustawiał w stosy. Teraz bawi się tak, że w każdym ruchu wybiera stos zawierający największą liczbę żetonów i dzieli go na dwa stosy mniej więcej w połowie. Dokładniej, jeśli stos przed podziałem miał $ \displaystyle m $ żetonów, to stosy powstałe w wyniku podziału mają rozmiary $ \displaystyle \lfloor m/2 \rfloor $ oraz $ \displaystyle \lceil m/2 \rceil $. Jeśli przed wykonaniem operacji jest więcej niż jeden stos o takiej samej, maksymalnej liczbie żetonów, Jaś wybiera dowolny z nich. Jaś kończy wykonywać ruchy w chwili, gdy każdy stos składa się już tylko z jednego żetonu.

Siostra Jasia, Małgosia, co jakiś czas przychodzi do Jasia i pyta go, ile ma różnych wysokości stosów monet. Jaś jest tak zajęty swoją zabawą, że nie ma czasu odpowiadać ciągle na pytania siostry. Poprosił Cię o napisanie programu, który będzie to robił za niego.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \le n \le 1000 $ ), oznaczająca początkową liczbę stosów. W drugim wierszu znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle m_i $ ( $ \displaystyle 1 \le m_i \le 10^6 $ ), oznaczających początkowe wysokości stosów. W trzecim wierszu znajduje się jedna liczba całkowita $ \displaystyle z $ ( $ \displaystyle 1 \le z \le 500\,000 $ ), oznaczająca liczbę pytań Małgosi. W czwartym wierszu znajduje się $ \displaystyle z $ liczb całkowitych $ \displaystyle k_i $ ( $ \displaystyle 1 \le k_i \le 10^9 $ ). Liczba $ \displaystyle k_1 $ oznacza, że pierwsze pytanie Małgosi nastąpiło po wykonaniu $ \displaystyle k_1 $ ruchów Jasia. Liczba $ \displaystyle k_2 $ oznacza, że drugie pytanie nastąpiło po wykonaniu kolejnych $ \displaystyle k_2 $ ruchów Jasia itd. Możesz założyć, że $ \displaystyle k_1+\ldots+k_z $ nie przekracza liczby ruchów wykonanych przez Jasia w całej grze.

Wyjście
Twój program powinien wypisać $ \displaystyle z $ wierszy. W $ \displaystyle i $-tym wierszu powinna znaleźć się jedna liczba całkowita oznaczająca liczbę różnych stosów żetonów, jakie ma Jaś w chwili, w której Małgosia zadała $ \displaystyle i $-te pytanie.

Przykład
Dla danych wejściowych:
3
9 8 2
3
1 2 3
poprawnym wynikiem jest:
4
3
2

Oto jak wyglądają wysokości stosów po kolejnych ruchach Jasia:

9, 8, 2
8, 5, 4, 2 (pierwsze pytanie Małgosi)
5, 4, 4, 4, 2
4, 4, 4, 3, 2, 2 (drugie pytanie Małgosi)
4, 4, 3, 2, 2, 2, 2
4, 3, 2, 2, 2, 2, 2, 2
3, 2, 2, 2, 2, 2, 2, 2, 2 (trzecie pytanie Małgosi).

Zadanie ZED (Żetony II), r. akad. 2013/2014, II termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Uwaga: Zadanie prostsze (Żetony I, ZET) różni się od trudniejszego (Żetony II, ZED) jedynie ograniczeniem na $ \displaystyle m_i $.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \le n \le 1000 $ ), oznaczająca początkową liczbę stosów. W drugim wierszu znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle m_i $ ( $ \displaystyle 1 \le m_i \le 10^9 $ ), oznaczających początkowe wysokości stosów. W trzecim wierszu znajduje się jedna liczba całkowita $ \displaystyle z $ ( $ \displaystyle 1 \le z \le 500\,000 $ ), oznaczająca liczbę pytań Małgosi. W czwartym wierszu znajduje się $ \displaystyle z $ liczb całkowitych $ \displaystyle k_i $ ( $ \displaystyle 1 \le k_i \le 10^9 $ ). Liczba $ \displaystyle k_1 $ oznacza, że pierwsze pytanie Małgosi nastąpiło po wykonaniu $ \displaystyle k_1 $ ruchów Jasia. Liczba $ \displaystyle k_2 $ oznacza, że drugie pytanie nastąpiło po wykonaniu kolejnych $ \displaystyle k_2 $ ruchów Jasia itd. Możesz założyć, że $ \displaystyle k_1+\ldots+k_z $ nie przekracza liczby ruchów wykonanych przez Jasia w całej grze.

Przykład
Dla danych wejściowych:
3
9 8 2
3
1 2 3
poprawnym wynikiem jest:
4
3
2

Oto jak wyglądają wysokości stosów po kolejnych ruchach Jasia:

9, 8, 2
8, 5, 4, 2 (pierwsze pytanie Małgosi)
5, 4, 4, 4, 2
4, 4, 4, 3, 2, 2 (drugie pytanie Małgosi)
4, 4, 3, 2, 2, 2, 2
4, 3, 2, 2, 2, 2, 2, 2
3, 2, 2, 2, 2, 2, 2, 2, 2 (trzecie pytanie Małgosi).

Zadanie GRA (Kolorowe grafy), r. akad. 2012/2013, I termin, zadanie prostsze

Dostępna pamięć: 256MB.

W czerwono-zielonym grafie jeden wierzchołek jest wyróżniony, a każda krawędź jest albo czerwona, albo zielona. Poza tym jest to zwykły graf nieskierowany.

Niech $ \displaystyle G $ będzie grafem czerwono-zielonym. Ścieżką w $ \displaystyle G $ nazywamy dowolny ciąg wierzchołków $ \displaystyle v_1,v_2,\ldots,v_k $, taki że każda para wierzchołków $ \displaystyle v_i, v_{i+1} $ (dla $ \displaystyle 1 \le i < k $ ) jest połączona krawędzią, a krawędzie te są na przemian czerwone i zielone (kolor pierwszej krawędzi ścieżki nie ma znaczenia). Naszym zadaniem jest znaleźć długość najkrótszej ścieżki z wierzchołka wyróżnionego do każdego innego wierzchołka grafu lub stwierdzić, że takiej ścieżki nie ma.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle m $ ( $ \displaystyle 2 \le n \le 500\,000 $, $ \displaystyle 1 \le m \le 500\,000 $ ), oznaczające liczbę wierzchołków i liczbę krawędzi grafu. Zakładamy, że wierzchołek wyróżniony ma numer 1. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera trzy liczby całkowite $ \displaystyle a_i $, $ \displaystyle b_i $ i $ \displaystyle k_i $ ( $ \displaystyle 1 \le a_i,b_i \le n $, $ \displaystyle a_i \ne b_i $, $ \displaystyle k_i \in \{0,1\} $ ), oznaczające końce krawędzi oraz jej kolor (0 - czerwona, 1 - zielona). Każda para wierzchołków jest połączona co najwyżej jedną krawędzią.

Wyjście
Twój program powinien wypisać $ \displaystyle n-1 $ wierszy. $ \displaystyle i $-ty z tych wierszy powinien zawierać jedną liczbę całkowitą: -1, jeśli
nie istnieje ścieżka z wierzchołka 1 do wierzchołka $ \displaystyle i+1 $, lub długość najkrótszej takiej ścieżki w przeciwnym przypadku.

Przykład
Dla danych wejściowych:
6 5
1 2 1
2 3 0
1 4 0
4 5 0
5 3 0
poprawnym wynikiem jest:
1
2
1
-1
-1
natomiast dla danych:
4 4
1 2 0
2 3 0
1 4 0
4 2 1
poprawnym wynikiem jest:
1
3
1

Zadanie MRO (Mrówki), r. akad. 2012/2013, I termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Na prostej stoi $ \displaystyle n $ mrówek. Każda mrówka znajduje się w jakimś punkcie całkowitym o współrzędnej z przedziału $ \displaystyle [1,n] $. Mrówki są bardzo małe, więc w jednym punkcie prostej może stać wiele mrówek.

Treser wydaje mrówkom polecenia następującej postaci: wszystkim mrówkom stojącym w punktach z przedziału $ \displaystyle [l,r] $ nakazuje przemieścić się do punktu $ \displaystyle d $ ( $ \displaystyle d \in [l,r] $ ). Treser chciałby wiedzieć, dla każdego polecenia, ile mrówek wskutek niego musiało zmienić swoje położenie.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ \displaystyle n $ i $ \displaystyle q $ ( $ \displaystyle 1 \le n,q \le 500\,000 $ ), oznaczające liczbę mrówek i liczbę wydanych poleceń. Drugi wiersz zawiera niemalejący ciąg $ \displaystyle n $ liczb całkowitych z zakresu od $ \displaystyle 1 $ do $ \displaystyle n $ - są to początkowe pozycje mrówek. Dalej następuje $ \displaystyle q $ wierszy z opisami poleceń. Każdy z tych wierszy zawiera trzy liczby całkowite $ \displaystyle l $, $ \displaystyle r $ i $ \displaystyle d $ ( $ \displaystyle 1 \le l \le d \le r \le n $ ).

Wyjście
Twój program powinien wypisać $ \displaystyle q $ wierszy z odpowiedziami na poszczególne zapytania. Każdy z tych wierszy powinien zawierać jedną liczbę całkowitą: liczbę mrówek, które zmieniły swoje położenie podczas wykonywania danego polecenia.

Przykład
Dla danych wejściowych:
5 3
1 2 2 4 5
3 5 3
1 1 1
1 2 2
poprawnym wynikiem jest:
2
0
1
natomiast dla danych:
6 2
1 2 3 4 5 6
1 4 2
3 6 5
poprawnym wynikiem jest:
3
1

Zadanie ZOL (Żołnierze), r. akad. 2012/2013, II termin, zadanie prostsze

Dostępna pamięć: 256MB.

W szeregu stoi $ \displaystyle n $ żołnierzy, ponumerowanych kolejno od 1 do $ \displaystyle n $ (od lewej do prawej). Generał będzie wydawał żołnierzom polecenie o nazwie obiad. Jeśli generał wyda to polecenie żołnierzowi o numerze $ \displaystyle i $, żołnierz ten będzie musiał najpierw wypowiedzieć na głos numer żołnierza, który stoi z jego lewej strony, potem wypowiedzieć numer żołnierza, który stoi z jego prawej strony, a następnie
udać się czym prędzej na obiad. Kiedy żołnierz znika z szeregu, pozostali żołnierze nieco się przesuwają, tak żeby w szeregu nie pozostała żadna dziura.

Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle n $ ( $ \displaystyle 1 \le n \le 500\,000 $ ), oznaczającą liczbę żołnierzy. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera po jednej liczbie całkowitej z zakresu od 1 do $ \displaystyle n $. Liczba zapisana w $ \displaystyle i $-tym wierszu oznacza numer żołnierza, któremu w $ \displaystyle i $-tym poleceniu generał rozkazał iść na obiad. Liczby w wierszach $ \displaystyle 2,3,\ldots,n+1 $ nie powtarzają się.

Wyjście
Twój program powinien wypisać $ \displaystyle n $ wierszy. $ \displaystyle i $-ty z tych wierszy powinien zawierać dwie liczby całkowite: numery lewego
i prawego sąsiada żołnierza, który w $ \displaystyle i $-tym poleceniu udaje się na obiad. Jeśli ów żołnierz w rozważanym momencie nie ma lewego lub prawego sąsiada, jako numer odpowiedniego sąsiada należy wypisać -1.

Przykład

Dla danych wejściowych:
5
4
2
1
5
3
poprawnym wynikiem jest:
3 5
1 3
-1 3
3 -1
-1 -1

Zadanie SKO (Skojarzenie), r. akad. 2012/2013, II termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Dane jest drzewo, czyli graf spójny o $ \displaystyle n $ wierzchołkach i $ \displaystyle n-1 $ krawędziach. Każda krawędź ma przypisaną wagę - pewną dodatnią liczbę całkowitą. Chcemy w tym drzewie znaleźć skojarzenie (czyli zbiór krawędzi, z których żadne dwie nie zawierają wspólnego wierzchołka) o maksymalnej sumie wag krawędzi.

Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 300\,000 $ ), oznaczającą liczbę wierzchołków drzewa. Wierzchołki są ponumerowane liczbami od 1 do $ \displaystyle n $. Każdy z kolejnych $ \displaystyle n-1 $ wierszy zawiera trzy liczby całkowite $ \displaystyle a_i $, $ \displaystyle b_i $, $ \displaystyle w_i $ ( $ \displaystyle 1 \le a_i, b_i \le n $, $ \displaystyle a_i \ne b_i $, $ \displaystyle 1 \le w_i \le 1000 $ ) oznaczające krawędź o wadze $ \displaystyle w_i $ łączącą wierzchołki $ \displaystyle a_i $ i $ \displaystyle b_i $. Podany na wejściu graf będzie drzewem, czyli nie będzie zawierał cykli.

Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą: wagę szukanego najcięższego skojarzenia w drzewie.

Przykład

Dla danych wejściowych:
7
1 3 2
3 2 1
2 4 5
2 5 7
3 6 10
6 7 1
poprawnym wynikiem jest:
17

Zadanie SZY (Szyna), r. akad. 2011/2012, I termin, zadanie prostsze

Dostępna pamięć: 256MB.

Profesor Makary zbudował układ elektroniczny złożony z $ \displaystyle n $ procesorów. Każdy z procesorów w danej chwili wykonuje pewien typ operacji; typy te oznaczamy dla uproszczenia liczbami całkowitymi (dodatnimi). Procesory mogą komunikować się wzdłuż jednej szyny danych.

Profesor chciałby oprogramować swój układ. W każdej jednostce czasu każdy procesor próbuje wysłać dane wzdłuż szyny do pewnego innego procesora, który w danej chwili wykonuje taki sam typ operacji. W danej jednostce czasu każdy procesor może albo wysyłać dane do jednego innego procesora, albo odbierać dane od jednego innego procesora.

Oprogramowanie profesora musi zabezpieczyć układ przed sytuacją, w której więcej niż jedna para procesorów próbowałaby przesyłać dane wzdłuż tego samego fragmentu szyny. Poza tym, oprogramowanie powinno dbać o to, aby w każdej jednostce czasu komunikowała się możliwie największa liczba par procesorów. Czy pomógłbyś profesorowi w napisaniu takiego oprogramowania?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 500\,000 $ ), oznaczająca liczbę procesorów. W drugim wierszu znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle p_i $ ( $ \displaystyle 1 \le p_i \le 10^9 $ ), pooddzielanych pojedynczymi odstępami i oznaczających typy operacji wykonywanych przez procesory w pewnej jednostce czasu. Procesory są podane w takiej kolejności, w jakiej są rozmieszczone wzdłuż szyny danych.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą nieujemną, oznaczającą maksymalną liczbę par procesorów, które mogą komunikować się w rozważanej jednostce czasu, z uwzględnieniem opisanych wyżej zasad komunikacji.

Przykład

Dla danych wejściowych:
11
6 4 1 4 1 4 4 6 3 7 3
poprawnym wynikiem jest:
3

Zadanie OSU (Osuszanie), r. akad. 2011/2012, I termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Bajtocja jest położona na stosunkowo bagnistym terenie. Krainę tę można przedstawić jako prostokąt złożony z $ \displaystyle n \cdot m $ pól, z których niektóre są przejezdne, a inne - zajęte przez bagna. Ostatnimi czasy kupcy mieszkający w miastach A i B postanowili wytyczyć szlak handlowy łączący te miasta, czyli sekwencję pól jednostkowych prowadzącą z miasta A do miasta B, w której każde dwa kolejne pola powinny sąsiadować bokiem.

Nie jest jasne, czy da się wytyczyć taką trasę bez osuszania bagien. Twoim zadaniem jest wyznaczyć minimalną liczbę pól z bagnami, jakie trzeba osuszyć, tak aby dało się poprowadzić co najmniej jeden szlak handlowy łączący miasta A oraz B.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 2 \le n, m \le 1\,000 $ ), oddzielone pojedynczym odstępem. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera $ \displaystyle m $ znaków, przy czym:

znak `.' oznacza wolne pole (przejezdne)
znak '#' oznacza bagno
znak `A' oznacza lokalizację miasta A
znak `B' oznacza lokalizację miasta B.

Możesz założyć, że w wejściu znajduje się dokładnie jedna litera `A' i dokładnie jedna litera `B'.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą nieujemną, oznaczającą liczbę pól, które trzeba osuszyć, tak aby istniała ścieżka łącząca miasta A i B.

Przykład

Dla danych wejściowych:
5 6
..#.A.
#####.
.#.#.#
.#.B#.
.#.#..
poprawnym wynikiem jest:
2

Zadanie TAB (Tablica), r. akad. 2011/2012, II termin, zadanie prostsze

Dostępna pamięć: 256MB.

Mamy daną tablicę rozmiaru $ \displaystyle n \times n $ wypełnioną liczbami całkowitymi. Chcielibyśmy stwierdzić, czy w jakimś wierszu tej tablicy są powtarzające się elementy, podobnie czy w jakiejś kolumnie są co najmniej dwa takie same elementy. Trzeba jednak dodać, że elementy tablicy mogą zmieniać się w czasie...

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 1\,000 $ ), oznaczająca rozmiar tablicy. W $ \displaystyle i $-tym z kolejnych $ \displaystyle n $ wierszy znajduje się $ \displaystyle n $ liczb całkowitych pooddzielanych pojedynczymi odstępami ( $ \displaystyle t_{i1},\ldots,t_{in} $ ), oznaczających poszczególne elementy $ \displaystyle i $-tego wiersza tablicy. W następnym wierszu znajduje się jedna liczba całkowita $ \displaystyle m $ ( $ \displaystyle 1 \le m \le 500\,000 $ ), oznaczająca liczbę zmian elementów tablicy. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera trzy liczby całkowite $ \displaystyle a_i $, $ \displaystyle b_i $ oraz $ \displaystyle k_i $ ( $ \displaystyle 1 \le a_i,b_i \le n $ ), pooddzielane pojedynczymi odstępami i oznaczające przypisania wartości elementów tablicy: element znajdujący się na przecięciu wiersza $ \displaystyle a_i $ i kolumny $ \displaystyle b_i $ zmienia swoją wartość na $ \displaystyle k_i $ ( $ \displaystyle t_{a_ib_i}:=k_i $ ). Wszystkie elementy, jakie kiedykolwiek znajdą się w tablicy, są liczbami całkowitymi z przedziału od $ \displaystyle 0 $ do $ \displaystyle 1\,000\,000 $.

Wyjście

Twój program powinien wypisać na standardowe wyjście $ \displaystyle m+1 $ wierszy. W $ \displaystyle i $-tym wierszu (dla $ \displaystyle 1 \le i \le m $ ) powinny znaleźć się dwa słowa oddzielone pojedynczym odstępem. Jeśli przed wykonaniem $ \displaystyle i $-tej operacji jakiś wiersz tablicy zawiera co najmniej dwie takie same liczby, pierwszym z tych słów powinno być TAK, w przeciwnym razie NIE. Podobnie, jako drugie słowo należy wypisać TAK, jeśli przed wykonaniem $ \displaystyle i $-tej operacji jakaś kolumna tablicy zawiera powtarzające się elementy, a w przeciwnym razie NIE. W wierszu o numerze $ \displaystyle m+1 $ należy wypisać słowa opisujące sytuację w tablicy po wykonaniu ostatniej operacji.

Przykład

Dla danych wejściowych:
3
1 2 3
4 5 6
7 8 9
3
1 2 3
2 2 3
1 2 8
poprawnym wynikiem jest:
NIE NIE
TAK NIE
TAK TAK
NIE TAK
natomiast dla danych:
3
1 2 3
1 2 9
5 6 7
14
2 1 3
2 2 3
2 3 3
2 2 7
2 3 7
2 3 8
3 2 7
2 3 7
1 3 7
3 3 6
2 2 6
2 3 6
2 2 10
3 3 10
poprawnym wynikiem jest:
NIE TAK
NIE TAK
TAK NIE
TAK TAK
TAK TAK
TAK TAK
NIE NIE
TAK TAK
TAK TAK
TAK TAK
TAK TAK
NIE TAK
TAK TAK
NIE TAK
NIE NIE

Zadanie KON (Koncentracja), r. akad. 2011/2012, II termin, zadanie trudnejsze

Dostępna pamięć: 256MB.

Powiemy, że zbiór punktów $ \displaystyle Z $ na płaszczyźnie jest $ \displaystyle d $-skoncentrowany, jeśli każde dwa punkty tego zbioru są oddalone od siebie o nie więcej niż $ \displaystyle d $. W szczególności, każdy jednoelementowy zbiór punktów jest $ \displaystyle d $-skoncentrowany dla dowolnego $ \displaystyle d \ge 0 $.

Mamy dany zbiór punktów $ \displaystyle A $ oraz parametr $ \displaystyle d $. Chcemy stwierdzić, czy punkty ze zbioru $ \displaystyle A $ można podzielić na dwa niepuste zbiory $ \displaystyle d $-skoncentrowane.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle d $ ( $ \displaystyle 2 \le n \le 2\,000 $, $ \displaystyle 0 \le d \le 2\,000\,000 $ ) oddzielone pojedynczym odstępem i oznaczające liczbę punktów w zbiorze $ \displaystyle A $ oraz parametr koncentracji. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera dwie liczby całkowite $ \displaystyle x_i $, $ \displaystyle y_i $ ( $ \displaystyle 0 \le x_y,y_i \le 1\,000\,000 $ ), oddzielone pojedynczym odstępem, oznaczające współrzędne $ \displaystyle i $-tego punktu w zbiorze $ \displaystyle A $. Punkty podane na wejściu nie będą się powtarzać.

Wyjście

W pierwszym wierszu wyjścia Twój program powinien wypisać jedno słowo TAK lub NIE, oznaczające, czy zbiór $ \displaystyle A $ można podzielić na dwa rozłączne i niepuste zbiory $ \displaystyle d $-skoncentrowane $ \displaystyle A_1 $ i $ \displaystyle A_2 $.

Jeśli odpowiedzią jest TAK, dwa kolejne wiersze powinny zawierać opis przykładowych zbiorów $ \displaystyle A_1 $ i $ \displaystyle A_2 $, po jednym opisie w wierszu. Opis zbioru $ \displaystyle A_i $ powinien zaczynać się od jednej liczby całkowitej dodatniej $ \displaystyle n_i $, oznaczającej liczbę punktów zawartych w tym zbiorze, a następnie $ \displaystyle n_i $ liczb całkowitych pooddzielanych pojedynczymi odstępami, oznaczających numery punktów przydzielonych do zbioru $ \displaystyle A_i $. Punkty numerujemy od 1 do $ \displaystyle n $ w kolejności występowania w wejściu.

Każda liczba całkowita z zakresu od $ \displaystyle 1 $ do $ \displaystyle n $ powinna pojawić się na liście elementów dokładnie jednego ze zbiorów $ \displaystyle A_1 $, $ \displaystyle A_2 $. Elementy zbiorów $ \displaystyle A_1 $ i $ \displaystyle A_2 $ można wypisać w dowolnej kolejności. Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać dowolne jedno z nich.

Przykład

Dla danych wejściowych:
7 3
5 3
1 1
4 2
1 3
5 2
2 3
5 1
jednym z poprawnych wyników jest:
TAK
3 6 4 2
4 1 3 5 7

Wyjaśnienie do przykładu: Podział opisany na wyjściu to $ \displaystyle A_1=\{(2,3),(1,3),(1,1)\} $, $ \displaystyle A_2=\{(5,3),(4,2),(5,2),(5,1)\} $.

Zadanie ODC (Odcinki), r. akad. 2010/2011, I termin, zadanie prostsze

Dostępna pamięć: 256MB.

Na płaszczyźnie narysowano $ \displaystyle n $ pionowych odcinków. Można by spytać, ile par odcinków się przecina, tzn. przecięcie ilu nieuporządkowanych par odcinków jest niepuste. No to spytajmy.

Nasze odcinki mają dodatkowo tę sympatyczną własność, że żadne dwa nie mają żadnego wspólnego końca.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 300\,000 $ ), oznaczająca liczbę odcinków. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera trzy liczby całkowite $ \displaystyle x $, $ \displaystyle y_1 $ i $ \displaystyle y_2 $ ( $ \displaystyle 0 \le x, y_1, y_2 \le 10^9 $, $ \displaystyle y_1 < y_2 $ ), pooddzielane pojedynczymi odstępami i oznaczające domknięty odcinek łączący punkty $ \displaystyle (x,y_1) $ i $ \displaystyle (x,y_2) $.

Wyjście

Na standardowe wyjście należy wypisać jeden wiersz zawierający jedną liczbę całkowitą: liczbę par przecinających się odcinków.

Przykład

Dla danych wejściowych:
5
3 1 5
4 2 6
3 2 7
3 3 4
4 7 8
poprawnym wynikiem jest:
3

Wyjaśnienie do przykładu: Przecinają się każde dwa odcinki o odciętej 3 i żadne inne.

Zadanie JAD (Jazda w kółko 2), r. akad. 2010/2011, I termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

W pewnym mieście jest $ \displaystyle n $ skrzyżowań połączonych pewną liczbą jednokierunkowych dróg (przy czym początkowe i końcowe skrzyżowanie każdej drogi są różne). Żadne drogi nie przecinają się poza skrzyżowaniami (w razie potrzeby drogi mogą prowadzić tunelami bądź estakadami). Należy stwierdzić, czy da się w tym mieście wyruszyć z jakiegoś skrzyżowania i przejechawszy pewną niezerową liczbą dróg zgodnie z ich orientacją, wrócić do tego samego skrzyżowania.

Należy zaznaczyć, że opis dróg sporządzono w postaci skondensowanej, opisanej dokładnie w następnym akapicie.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1\le n\le 300\,000 $, $ \displaystyle 0\le m\le 300\,000 $ ), oddzielone pojedynczym odstępem. Kolejne $ \displaystyle m $ wierszy zawiera opisy grup dróg, po jednym w wierszu. Każdy opis składa się z trzech liczb całkowitych $ \displaystyle a_i $, $ \displaystyle b_i $ oraz $ \displaystyle c_i $ ( $ \displaystyle 1\le a_i \le n $ , $ \displaystyle 1 \le b_i \le c_i \le n $ ), oznaczających, że ze skrzyżowania numer $ \displaystyle a_i $ do każdego ze skrzyżowań $ \displaystyle b_i,\ldots,c_i $ prowadzi jednokierunkowa droga.

Możesz założyć, że nie istnieją dwie drogi mające zarówno to samo skrzyżowanie początkowe jak i końcowe.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedno słowo TAK, jeżeli w mieście istnieje opisana powyżej trasa, lub NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:
4 5
1 2 3
1 4 4
2 3 4
3 4 4
4 1 1
poprawnym wynikiem jest:
TAK

Przykładem szukanej trasy jest $ \displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4 \rightarrow 1 $.

natomiast dla danych:
4 4
1 2 3
1 4 4
2 3 4
3 4 4
poprawnym wynikiem jest:
NIE

Zadanie ROD (Różnica 2), r. akad. 2010/2011, II termin, zadanie prostsze

Dostępna pamięć: 64MB.

Będziemy wykonywać operacje na zbiorze liczb całkowitych $ \displaystyle A $. Na początku $ \displaystyle A = \emptyset $. Każda operacja polega na dodaniu do zbioru elementu, którego w tym zbiorze aktualnie nie ma, bądź usunięciu elementu, który znajduje się aktualnie w zbiorze. Po każdej operacji chcielibyśmy wiedzieć, czy w zbiorze są jakieś dwie liczby różniące się dokładnie o $ \displaystyle d $.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle d $ ( $ \displaystyle 1 \le n \le 300\,000 $, $ \displaystyle 1 \le d \le 10^9 $ ), oddzielone pojedynczym odstępem. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera dwie liczby całkowite $ \displaystyle c_i,a_i $ ( $ \displaystyle 0 \le a_i \le 10^9 $, $ \displaystyle c_i \in \{-1,1\} $ ) oddzielone pojedynczym odstępem i opisujące pojedynczą operację na zbiorze. Jeżeli $ \displaystyle c_i=1 $, to jest to operacja dodania elementu $ \displaystyle a_i $, a w przeciwnym przypadku usuwamy ten element ze zbioru.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie $ \displaystyle n $ wierszy, z których $ \displaystyle i $-ty (dla $ \displaystyle i=1,2,\ldots,n $ ) powinien zawierać jedno słowo TAK lub NIE, w zależności od tego, czy po wykonaniu pierwszych $ \displaystyle i $ operacji zbiór $ \displaystyle A $ zawiera parę liczb różniących się dokładnie o $ \displaystyle d $ czy nie.

Przykład

Dla danych wejściowych:
7 4
1 2
1 10
1 6
-1 2
-1 6
1 9
1 14
poprawnym wynikiem jest:
NIE
NIE
TAK
TAK
NIE
NIE
TAK

Zadanie WZO (Wzorzec), r. akad. 2010/2011, II termin, zadanie trudniejsze

Dostępna pamięć: 64MB.

Mamy dany graf skierowany $ \displaystyle G $, którego krawędzie są etykietowane niepustymi słowami złożonymi z małych liter alfabetu angielskiego. Dla danego słowa $ \displaystyle s $ chcemy sprawdzić, czy istnieje w grafie taki spacer (ścieżka z możliwymi powtórzeniami), że po złączeniu słów z kolejno przechodzonych krawędzi otrzymamy słowo $ \displaystyle s $. Podkreślmy, że przy złączaniu słów leżących na krawędziach bierzemy zawsze całe słowa.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1 \le n \le 100 $, $ \displaystyle 0 \le m \le 1\,000 $ ), oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę wierzchołków i krawędzi grafu $ \displaystyle G $. Każdy z kolejnych $ \displaystyle m $ wierszy zawiera opis pojedynczej krawędzi. Opis taki składa się z dwóch liczby całkowitych $ \displaystyle a_i,b_i $ ( $ \displaystyle 1 \le a_i, b_i \le n $ , $ \displaystyle a_i \neq b_i $ ) oraz niepustego słowa $ \displaystyle s_i $ złożonego z małych liter alfabetu angielskiego ( $ \displaystyle 1 \le |s_i| \le 1\,000 $ ). Elementy występujące w opisie krawędzi są oddzielone pojedycznymi odstępami. Opisywana krawędź prowadzi od wierzchołka $ \displaystyle a_i $ do wierzchołka $ \displaystyle b_i $ i jest etykietowana słowem $ \displaystyle s_i $. Pomiędzy parą wierzchołków może być dowolnie wiele krawędzi.

Ostatni wiersz standardowego wejścia zawiera słowo $ \displaystyle s $, składające się z małych liter alfabetu angielskiego ( $ \displaystyle 1 \le |s| \le 100\,000 $ ).

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie jeden wiersz, zawierający jedno słowo TAK lub NIE, w zależności od tego, czy w danym grafie istnieje poszukiwany spacer.

Przykład

Dla danych wejściowych:
3 4
1 2 abc
2 1 a
1 2 aaa
2 3 xyz
abcaaaaxyz
poprawnym wynikiem jest:
TAK

natomiast dla danych:
2 3
1 2 aa
2 1 aa
1 2 aa
aaaaa
poprawnym wynikiem jest:
NIE

Zadanie ROZ (Różnica), r. akad. 2009/2010, I termin, zadanie prostsze

Dostępna pamięć: 64MB.

Dany jest ciąg liczb całkowitych $ \displaystyle a_1,a_2,\ldots,a_n $. Napisz program, który sprawdzi, czy w tym ciągu znajdują się dwie liczby różniące się dokładnie o $ \displaystyle d $.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle d $ ( $ 1 \le n \le 300\,000 $, $ \displaystyle -10^9 \le d \le 10^9 $ ), oddzielone pojedynczym odstępem. Drugi wiersz zawiera $ \displaystyle n $ liczb całkowitych $ \displaystyle a_1,a_2,\ldots,a_n $ ( $ \displaystyle -10^9 \le a_i \le 10^9 $ ), pooddzielanych pojedynczymi odstępami.

Wyjście

Jeśli w ciągu $ \displaystyle a $ nie ma żadnej pary elementów różniących się o $ \displaystyle d $, Twój program powinien wypisać na standardowe wyjście jedno słowo NIE. W przeciwnym przypadku Twój program powinien wypisać dwie liczby całkowite $ \displaystyle u,v $ oddzielone pojedynczym odstępem, reprezentujące dwa wyrazy ciągu $ \displaystyle a $ różniące się o $ \displaystyle d $ ( $ \displaystyle u=a_i $, $ \displaystyle v=a_j $, $ \displaystyle i \ne j $, $ \displaystyle u-v=d $ ). Jeżeli istnieje więcej niż jedna poprawna odpowiedź, Twój program może wypisać dowolną z nich.

Przykład

Dla danych wejściowych:
5 3
5 3 4 -2 2
poprawnym wynikiem jest:
5 2

natomiast dla danych:
5 -3
5 3 4 -2 2
poprawnym wynikiem jest:
2 5

natomiast dla danych:
4 1
2 2 2 2
poprawnym wynikiem jest:
NIE

Zadanie DEG (Degeneraty), r. akad. 2009/2010, I termin, zadanie trudniejsze

Dostępna pamięć: 64MB.

Graf $ \displaystyle H = (V_1, E_1) $ jest podgrafem grafu $ \displaystyle G = (V, E) $, jeśli $ \displaystyle V_1 \subseteq V $, $ \displaystyle E_1 \subseteq E $ i $ \displaystyle E_1 \subseteq V_1 \times V_1 $. Mówimy, że graf $ \displaystyle G $ jest $ \displaystyle d $-degeneratem (dla pewnej liczby całkowitej dodatniej $ \displaystyle d $ ), jeśli w każdym podgrafie grafu $ \displaystyle G $ istnieje wierzchołek o stopniu co najwyżej $ \displaystyle d $. Dla danego grafu $ \displaystyle G $ wyznacz najmniejszą liczbę całkowitą dodatnią $ \displaystyle d $ taką, że $ \displaystyle G $ jest $ \displaystyle d $-degeneratem.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1\le n, m\le 500\,000 $ ), oddzielone pojedynczym odstępem, oznaczające liczby wierzchołków i krawędzi grafu $ \displaystyle G $. Wierzchołki są ponumerowane liczbami naturalnymi $ \displaystyle 1, 2, \ldots, n $. Kolejne $ \displaystyle m $ wierszy opisuje krawędzie: każdy z nich zawiera dwie liczby naturalne $ \displaystyle 1 \leq a_i, b_i \leq n $, $ \displaystyle a_i \neq b_i $ oznaczające krawędź między wierzchołkiami $ \displaystyle a_i $ i $ \displaystyle b_i $. Żadna para $ \displaystyle \{a_i, b_i\} $ nie pojawia się na wejściu więcej niż raz.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - najmniejszą liczbę całkowitą dodatnią $ \displaystyle d $ taką, że $ \displaystyle G $ jest $ \displaystyle d $-degeneratem.

Przykład

Dla danych wejściowych:
12 16
1 2
2 3
3 1
3 4
4 5
5 8
5 9
5 10
6 8
6 9
6 10
7 8
7 9
7 10
10 11
11 12
poprawnym wynikiem jest:
3

Wyjaśnienie do przykładu: Wierzchołki $ \displaystyle \{5, 6, 7, 8, 9, 10\} $ oraz wszystkie krawędzie między nimi tworzą podgraf, w którym każdy wierzchołek ma stopień co najmniej 3, patrz także poniższy rysunek.

Ilustracja przykładu w zadaniu DEG

Zadanie PRZ (Przedziały), r. akad. 2009/2010, II termin, zadanie prostsze

Dostępna pamięć: 64MB.

Dane jest $ \displaystyle n $ przedziałów domkniętych $ \displaystyle [a_i,b_i] $. Jaka jest minimalna wartość bezwzględna różnicy dwóch
liczb należących do dwóch różnych przedziałów? Formalnie, chcemy obliczyć

$ \displaystyle \min\{ |x-y|\ :\ x \in [a_i,b_i],\ y \in [a_j, b_j],\ 1 \le i < j \le n\} $.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita $ \displaystyle n $ ( $ \displaystyle 2 \le n \le 500\,000 $ ) - liczba przedziałów. Każdy z kolejnych $ \displaystyle n $ wierszy zawiera dwie liczby całkowite $ \displaystyle a_i $ oraz $ \displaystyle b_i $ ( $ \displaystyle 0 \le a_i \le b_i \le 10^9 $ ), oddzielone pojedynczym odstępem i reprezentujące końce $ \displaystyle i $-tego przedziału domkniętego $ \displaystyle [a_i,b_i] $. Można założyć, że wszystkie pary $ \displaystyle (a_i,b_i) $ są różne.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający liczbę całkowitą zdefiniowaną w treści zadania.

Przykład

Dla danych wejściowych:
2
1 2
3 4
poprawnym wynikiem jest:
1

Zadanie CYK (Cykl), r. akad. 2009/2010, II termin, zadanie trudniejsze

Dostępna pamięć: 64MB.

Mamy dany graf nieskierowany $ \displaystyle G=(V,E) $ oraz zbiór dodatkowych krawędzi $ \displaystyle E_1 $, których możemy użyć bądź nie ( $ \displaystyle E \cap E_1 = \emptyset $ ). Ile maksymalnie krawędzi ze zbioru $ \displaystyle E_1 $ możemy dołożyć do grafu, tak aby graf zawierał dokładnie jeden cykl prosty?

Przypomnijmy, że cykl prosty to taki cykl, w którym wierzchołki nie powtarzają się.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite $ \displaystyle n $, $ \displaystyle m $ oraz $ \displaystyle k $ ( $ \displaystyle 2 \le n \le 500\,000 $, $ \displaystyle 0 \le m,k \le 1\,000\,000 $ ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę wierzchołków ( $ \displaystyle |V| $ ) i liczbę krawędzi grafu ( $ \displaystyle |E| $ ) oraz liczbę dodatkowych krawędzi, których możemy użyć ( $ \displaystyle |E_1| $ ). Każdy z kolejnych $ \displaystyle m $ wierszy zawiera dwie liczby całkowite $ \displaystyle a_i $ oraz $ \displaystyle b_i $ ( $ \displaystyle 1 \le a_i < b_i \le n $ ), oddzielone pojedynczym odstępem i oznaczające numery wierzchołków będących końcami $ \displaystyle i $-tej krawędzi ze zbioru $ \displaystyle E $. Dalej następuje $ \displaystyle k $ wierszy, z których każdy zawiera dwie liczby całkowite $ \displaystyle c_i $ oraz $ \displaystyle d_i $ ( $ \displaystyle 1 \le c_i < d_i \le n $ ), oddzielone pojedynczym odstępem i oznaczające numery wierzchołków będących końcami $ \displaystyle i $-tej krawędzi dodatkowej ze zbioru $ \displaystyle E_1 $. Można założyć, że wszystkie pary $ \displaystyle (a_i,b_i) $ oraz $ \displaystyle (c_i,d_i) $ są różne.

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą: maksymalną liczbę krawędzi ze zbioru $ \displaystyle E_1 $, po których dodaniu do początkowego grafu $ \displaystyle (V,E) $ graf zawiera dokładnie jeden cykl prosty, lub $ \displaystyle -1 $, jeżeli nie da się tak dobrać krawędzi ze zbioru $ \displaystyle E_1 $, żeby wynikowy graf zawierał dokładnie jeden cykl prosty.

Przykład

Dla danych wejściowych:
9 6 3
1 2
2 3
2 4
5 6
5 7
8 9
1 5
4 6
3 7
poprawnym wynikiem jest:
2

Ilustracja pierwszego przykładu w zadaniu CYK

natomiast dla danych:
8 8 2
1 2
2 3
3 4
1 4
5 6
6 7
7 8
5 8
1 3
2 4
poprawnym wynikiem jest:
-1

Ilustracja drugiego przykładu w zadaniu CYK

Wyjaśnienie do przykładu: Kółka na powyższych rysunkach przedstawiają wierzchołki, odcinki - krawędzie grafu, a odcinki przerywane - dodatkowe krawędzie. W pierwszym przykładzie po dodaniu dowolnych dwóch krawędzi graf zawiera dokładnie jeden cykl prosty, natomiast w drugim stworzenie grafu z dokładnie jednym cyklem prostym nie jest możliwe.

Zadanie JED (Jedynki), r. akad. 2008/2009, I termin, zadanie prostsze

Dostępna pamięć: 64MB.

Mamy dany ciąg $ \displaystyle n $ liczb naturalnych $ \displaystyle a=a_1, a_2, \ldots, a_n $. Twoim zadaniem jest wyznaczenie liczby jedynek w zapisie binarnym każdej z sum $ \displaystyle \sum_{i=1}^{k}2^{a_i} $ dla $ \displaystyle k=1,2,\ldots,n $.

Wejście

W pierwszym wierszu znajduje się liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \leq n \leq 500\,000 $ ) - liczba elementów ciągu. W drugim wierszu znajduje się $ \displaystyle n $ liczb całkowitych $ \displaystyle a_i $ ( $ \displaystyle 0 \le a_i \le 500\,000 $ ) pooddzielanych pojedynczymi odstępami.

Wyjście

Twój program powinien wypisać $ \displaystyle n $ liczb całkowitych - $ \displaystyle k $-ty wiersz powinien zawierać liczbę jedynek w rozwinięciu binarnym odpowiedniej sumy $ \displaystyle k $ potęg dwójki.

Przykład

Dla danych wejściowych:
4
0 1 2 1
poprawnym wynikiem jest:
1
2
3
2

Wyjaśnienie do przykładu: szukane sumy to kolejno: 1, 3, 7, 9.

Zadanie POD (Podciągi), r. akad. 2008/2009, I termin, zadanie trudniejsze

Dostępna pamięć: 64MB.

Mamy dane ciąg liczb naturalnych $ \displaystyle a=a_1,a_2,\ldots,a_n $ oraz liczbę naturalną $ \displaystyle k $. Ile spójnych (tj. jednokawałkowych) podciągów ciągu $ \displaystyle a $ składa się z co najwyżej $ \displaystyle k $ różnych elementów?

Podciągi uznajemy za różne, jeżeli ich umiejscowienia w ramach ciągu $ \displaystyle a $ są różne. Dodatkowo, rozważamy jedynie podciągi dodatniej długości.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle k $ ( $ \displaystyle 1\le n, k\le 500\,000 $ ), oddzielone pojedynczym odstępem. Drugi wiersz wejścia zawiera $ \displaystyle n $ liczb całkowitych $ \displaystyle a_i $ ( $ \displaystyle 0\le a_i\le 1\,000\,000\,000 $ ), pooddzielanych pojedynczymi odstępami.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - liczbę spójnych podciągów ciągu $ \displaystyle a $, złożonych z co najwyżej $ \displaystyle k $ różnych elementów.

Przykład

Dla danych wejściowych:
5 2
4 2 3 2 3
poprawnym wynikiem jest:
12

Wyjaśnienie do przykładu: Szukane podciągi to:

pięć ciągów jednoelementowych, z których dwa, tzn. (2) i (3), liczone są dwukrotnie;
cztery ciągi dwuelementowe: (4, 2), (2, 3), (3, 2) i (2, 3);
dwa ciągi trzyelementowe: (2, 3, 2) i (3, 2, 3);
jeden ciąg czteroelementowy (2, 3, 2, 3).

Zauważ, że ciąg (2, 2, 3) jest podciągiem wyjściowego ciągu i zawiera dokładnie dwa różne elementy, jednakże nie jest on spójny.

Zadanie JAZ (Jazda w kółko), r. akad. 2008/2009, II termin, zadanie prostsze

Dostępna pamięć: 256MB.

W pewnym mieście jest $ \displaystyle n $ skrzyżowań i $ \displaystyle m $ dróg, z których każda jest dwukierunkowa oraz zaczyna się i kończy przy jakimś skrzyżowaniu (przy czym początkowe i końcowe skrzyżowanie każdej drogi są różne). Żadne drogi nie przecinają się poza skrzyżowaniami (w razie potrzeby drogi mogą prowadzić tunelami bądź estakadami). Należy stwierdzić, czy da się w tym mieście wyruszyć z jakiegoś skrzyżowania i przejechawszy pewną niezerową liczbą dróg (żadną drogą nie można przy tym przejechać dwukrotnie), wrócić do tego samego skrzyżowania.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite $ \displaystyle n $ oraz $ \displaystyle m $ ( $ \displaystyle 1\le n\le 200\,000 $, $ \displaystyle 0\le m\le 500\,000 $ ), oddzielone pojedynczym odstępem. Kolejne $ \displaystyle m $ wierszy zawiera opisy dróg, po jednym w wierszu. Każdy opis składa się z dwóch liczb całkowitych $ \displaystyle a_i $ oraz $ \displaystyle b_i $ ( $ \displaystyle 1\le a_i < b_i\le n $ ), oznaczających numery skrzyżowań połączonych drogą. Każde dwa skrzyżowania są połączone co najwyżej jedną drogą.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedno słowo TAK, jeżeli w mieście istnieje opisana powyżej trasa, lub NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:
6 7
1 2
1 3
1 4
2 3
2 4
3 4
5 6
poprawnym wynikiem jest:
TAK

Wyjaśnienie. Przykładem szukanej trasy jest $ \displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 1 $.

Natomiast dla danych:
4 3
1 2
2 3
3 4
poprawnym wynikiem jest:
NIE

Zadanie KRO (Krotności), r. akad. 2008/2009, II termin, zadanie trudniejsze

Dostępna pamięć: 256MB.

Dane jest $ \displaystyle n $ przedziałów $ \displaystyle [a_i,b_i] $ z krotnościami. Krotność $ \displaystyle i $-tego przedziału wynosi $ \displaystyle k_i $. Dla liczby całkowitej $ \displaystyle x $ przez $ \displaystyle \mathrm{kro}(x) $ oznaczmy sumę krotności przedziałów, do których należy $ \displaystyle x $. Twoim zadaniem jest wyznaczenie liczby par nieuporządkowanych $ \displaystyle \{x,y\} $, takich że $ \displaystyle \mathrm{kro}(x) > 0 $, $ \displaystyle \mathrm{kro}(y) > 0 $ oraz $ \displaystyle \mathrm{kro}(x) \ne \mathrm{kro}(y) $.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita $ \displaystyle n $ ( $ \displaystyle 1 \leq n \leq 500\,000 $ ) - liczba przedziałów. W kolejnych $ \displaystyle n $ wierszach znajdują się opisy przedziałów. Opis przedziału składa się z trzech liczb całkowitych $ \displaystyle a_i,b_i,k_i $ ( $ \displaystyle 1\le a_i \le b_i \le 10^9, 1 \le k_i \le 1\,000 $ ) pooddzielanych pojedynczymi odstępami, będących odpowiednio końcami przedziału oraz jego krotnością.

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą - liczbę szukanych par liczb.

Przykład

Dla danych wejściowych:
3
1 3 2
3 4 3
3 5 1
poprawnym wynikiem jest:
9

Wyjaśnienie do przykładu: Szukane pary to: $ \displaystyle \{1,3\},\ \{1,4\},\ \{1,5\},\ \{2,3\},\ \{2,4\},\ \{2,5\},\ \{3,4\},\ \{3,5\},\ \{4,5\} $.

Załącznik	Wielkość
jed.cpp	695 bajtów
pod.cpp	766 bajtów
jaz.cpp	901 bajtów
kro.cpp	1.17 KB
roz.cpp	628 bajtów
deg.cpp	926 bajtów
prz.cpp	602 bajty
cyk.cpp	1.25 KB
odc.cpp	696 bajtów
jad.cpp	1.42 KB
rod.cpp	569 bajtów
wzo.cpp	1.48 KB
szy.cpp	395 bajtów
osu.cpp	1.43 KB
tab1.cpp	1.05 KB
tab2.cpp	1.03 KB
kon.cpp	1.53 KB
gra.cpp	1.31 KB
mro.cpp	806 bajtów
zol.cpp	876 bajtów
zol2.cpp	633 bajty
sko.cpp	1006 bajtów
zet.cpp	1.2 KB
zed.cpp	696 bajtów
ski.cpp	851 bajtów
pre.cpp	1.33 KB
wzn.cpp	759 bajtów
aut.cpp	1.41 KB
autrys1-crop.jpg	14.37 KB
autrys2-crop.jpg	16.94 KB
par.cpp	782 bajty
parrys-crop.jpg	10.33 KB
pad.cpp	1.72 KB
est.cpp	1.38 KB
pot.cpp	1.23 KB
nas.cpp	1.7 KB
tra.cpp	1.29 KB
trazad.jpg	43.56 KB

Laboratoria

Laboratorium 1: złożoność obliczeniowa w praktyce

Zadanie BAZ (Bazarek)

Dostępna pamięć: 128MB.

Termin: 27.10.2019, 23:59:59

Zadanie MAT (Matryca)

Dostępna pamięć: 128MB.

Termin: 27.10.2019, 23:59:59

Laboratorium 2: programowanie dynamiczne

Zadanie SOR (Sortowanie komórkowe)

Dostępna pamięć: 64MB.

Laboratorium 3: proste techniki

Zadanie MEC (Mecze)

Dostępna pamięć: 128 MB.

Zadanie zaliczeniowe 1

Zadanie KRE (Kreatywna Księgowość), r. akad. 2017/2018

Dostępna pamięć: 128MB.

Archiwum

Zadanie REL (Relaks), r. akad. 2016/2017

Dostępna pamięć: 128MB.

Zadanie WYK (Wykopaliska), r. akad. 2014/2015

Dostępna pamięć: 128MB.

Zadanie BAJ (Bajtobity), r. akad. 2013/2014

Dostępna pamięć: 64MB.

Zadanie PEN (Pensja), r. akad. 2012/2013

Dostępna pamięć: 32MB.

Zadanie TRA (Transport), r. akad. 2011/2012

Dostępna pamięć: 32MB.

Zadanie NAW (Nawiasy), r. akad. 2010/2011

Dostępna pamięć: 64MB.

Zadanie PRO (Procenty), r. akad. 2009/2010

Dostępna pamięć: 256MB.

Zadanie WIR (Wirówka liczbowa), r. akad. 2008/2009

Dostępna pamięć: 32MB.

Laboratorium 4: drzewo przedziałowe

Zadanie KIN ( \( \displaystyle k \)-inwersje)

Dostępna pamięć: 64MB.

Laboratorium 5: drzew przedziałowych ciąg dalszy

Zadanie MAL (Malowanie autostrady)

Dostępna pamięć: 128MB.

Laboratorium 6: ciąg dalszy struktur danych

Zadanie PAR (Park Bitowy)

Dostępna pamięć: 128MB.

Zadanie zaliczeniowe 2

Zadanie PRZ (Przedziały), r. akad. 2014/2015

Dostępna pamięć: 128MB.

Archiwum

Zadanie OBC (Obciążenie drogi), r. akad. 2013/2014

Dostępna pamięć: 128MB.

Zadanie PRD (Prodziekan do spraw studenckich), r. akad. 2012/2013

Dostępna pamięć: 64MB.

Zadanie RDZ (Rdza), r. akad. 2011/2012

Dostępna pamięć: 32MB.

Zadanie CIA (Ciasta), r. akad. 2010/2011

Dostępna pamięć: 64MB.

Zadanie CIE (Cięciwy), r. akad. 2009/2010

Dostępna pamięć: 128MB.

Zadanie MAL (Malowanie autostrady), r. akad. 2008/2009

Dostępna pamięć: 128MB.

Laboratorium 7: zastosowanie biblioteki STL

Zadanie PRJ (Projekty)

Dostępna pamięć: 256MB.

Laboratorium 8: biblioteki STL ciąg dalszy i jeden ważny a klasyczny algorytm

Zadanie KAP (Kapitan)

Dostępna pamięć: 256MB.

Laboratorium 9: odrobina algorytmów tekstowych

Zadanie LEX (Porównywanie leksykograficzne)

Dostępna pamięć: 64MB.

Laboratorium 10: Find & Union

Zadanie INW (Graf inwersji)

Dostępna pamięć: 128MB.

Zadanie karne

Zadanie ULA (Ula), r. akad. 2014/2015

Dostępna pamięć: 128MB.

Archiwum

Zadanie PPL (Podpalindrom), r. akad. 2013/2014

Dostępna pamięć: 32MB.

Zadanie ROB (Roboty), r. akad. 2012/2013

Dostępna pamięć: 256MB.

Zadanie KUR (Kurort), r. akad. 2011/2012