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.
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:
Przykład
Dla danych wejściowych:
5
6
2
0
-1
poprawnym wynikiem jest:
15
2 3
4
4 5
1
1 1
0
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
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:
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.
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
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
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