Mamy 4 prostokąty o wymiarach A[i]xB[i], i=1,2,3,4. Jakie jest pole najmniejszego prostokąta, w którym można umieścić wspomniane 4 prostokąty, jeśli nie mogą one nachodzić na siebie?
Dane: 1 ≤ i ≤ 4; 1 ≤ A[i], B[i] ≤ 1.000
Wejście: A[1] B[1] A[2] B[2] A[3] B[3] A[4] B[4] {1 1 2 2 3 3 4 4}
Wyjście: pole {35}
Czas działania pewnego komputera podzielony jest na jednostki czasu 1..M. Wykonuje się na nim N zadań. Zadanie i zaczyna się w jednostce a[i], a kończy w jednostce b[i] (włącznie). Zadania mogą zachodzić na siebie. Jak długi jest najdłuższy okres bezczynności, tj. okres czasu, kiedy komputer nie wykonuje żadnego zadania?
Dane: 1 ≤ N ≤ 5.000; 1 ≤ M ≤ 109, 1 ≤ i ≤ N; 1 ≤ a[i] ≤ b[i] ≤ M
Wejście: N M a[1] b[1] a[2] b[2] ... a[N] b[N] {3 9 2 3 7 9 6 7}
Wyjście: maksymalny_okres_bezczynności {2}
Mamy daną listę długości odcinków a[1..N] będących liczbami całkowitymi nie większymi od M. Czy istnieją takie trzy odcinki (o różnych indeksach), z których da się zbudować trójkąt o niezerowym polu?
Dane: 1 ≤ N ≤ 107; 1 ≤ M ≤ 109; 1 ≤ i ≤ N; 1 ≤ a[i] ≤ M
Wejście: N M a[1] a[2] ... a[N] {4 10 4 2 3 1}
Wyjście: TAK/NIE {TAK}
Mamy N zadań. Każde zadanie jest scharakteryzowane przez współczynnik a[i] oraz b[i]. Jeżeli zadanie i rozpocznie się w chwili t, to trwa a[i]*t+b[i] jednostek czasu. Wiedząc, że komputer zaczyna działać w chwili 0 oraz że zadania nie mogą zachodzić na siebie, uporządkuj je tak, aby ich łączny czas wykonania był minimalny. Podaj łączny (optymalny) czas wykonywania zadań modulo 99991.
Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; 0 ≤ a[i], b[i] ≤ 10.000
Wejście: N a[1] b[1] a[2] b[2] ... a[N] b[N] {3 1 3 3 1 2 2}
Wyjście: czas_wykonywania {13}
Mamy N punktów, z których żadne 3 nie są współliniowe. Trzeba tak połączyć punkty odcinkami, aby z i-tego punktu wychodziło dokładnie A[i] odcinków. Odcinki nie mogą się powtarzać. Wynikiem jest albo NIE, jeśli jest to niemożliwe, albo lista par indeksów (dowolna, jeśli jest kilka możliwości), takich że każda para odpowiada jednemu odcinkowi, a elementy pary są numerami punktów, będących jego końcami (punkty ponumerowane są od 1 do N).
Dane: 1 ≤ N ≤ 1.000; 1 ≤ i ≤ N; 0 ≤ A[i] ≤ N–1
Wejście: N A[1] A[2] ... A[N] {5 1 3 2 3 1}
Wyjście: lista_końców lub NIE {1 2 2 3 2 4 3 4 4 5}
Samochód jedzie z miasta A miasta B. Trasa ma łączną długość D. Po drodze mija N stacji benzynowych - na stacji i odległej od początku o L[i] sprzedawca oferuje nieograniczoną ilość paliwa po cenie X[i] za jednostkę. Pojemność baku samochodu wynosi W (samochód startuje z pełnym bakiem), a każda jednostka paliwa starcza na przejechanie jednej jednostki odległości. Wyznacz najmniejszą cenę, za jaką da się dojechać z A do B. Stacje benzynowe są posortowane rosnąco względem ich odległości od początku trasy.
Dane: 1 ≤ N ≤ 106; 1 ≤ D ≤ 107; 1 ≤ W ≤ D; 1 ≤ i ≤ N; 1 ≤ L[i] ≤ D; 1 ≤ X[i] ≤ 100
Wejście: N D W L[1] X[1] L[2] X[2] ... L[N] X[N] {2 10 5 3 6 7 1}
Wyjście: minimalna_cena {15}
Mamy N jednakowych produktów oraz M maszyn. Każda maszyna ma określony czas A[i], przez który przetwarza produkt. Maszyna może przetwarzać co najwyżej 1 produkt jednocześnie. Jaki jest minimalny czas przetworzenia wszystkich produktów przez maszyny.
Dane: 1 ≤ N ≤ 1.000; 1 ≤ M ≤ 1.000; 1 ≤ i ≤ M; 1 ≤ A[i] ≤ 100
Wejście: N M A[1] A[2] ... A[M] {3 2 2 3}
Wyjście: minimalny_czas_przetwarzenia {4}
W tej wersji zadania mamy 2 rodzaje maszyn: MA typu A i MB maszyn typu B. Ich czasy przetwarzania oznaczone są odpowiednio A[i] oraz B[j]. Każdy produkt musi najpierw być przetworzony przez maszynę typu A, a później przez maszynę typu B. Jaki jest minimalny czas przetworzenia wszystkich produktów przez maszyny obu typów?
Dane: 1 ≤ N ≤ 1.000; 1 ≤ MA, MB ≤ 1.000; 1 ≤ i ≤ MA; 1 ≤ j ≤ MB; 1 ≤ A[i], B[j] ≤ 100
Wejście: N MA MB A[1] ... A[MA] B[1] ... B[MB] {3 2 3 2 3 2 3 1}
Wyjście: minimalny_czas_przetwarzania {5}
W kwadracie MxM mamy N punktów (x[i],y[i]). Jaki jest największy prostokąt zawierający się w dużym kwadracie (o bokach równoległych do jego boków), w którego środku nie ma żadnego z danych punktów?
Dane: 1 ≤ M ≤ 1.000; 1 ≤ N ≤ 1.000; 1 ≤ i ≤ N; 0 ≤ x[i], y[i] ≤ M
Wejście: N M x[1] y[1] ... x[N] y[N] {4 7 2 2 5 5 1 6 6 1}
Wyjście: maksymalne_pole {21}
Mamy jednowymiarową szachownicę złożoną z N pól i na każdym z nich stoi jeden pionek. Pionek o numerze i stoi na polu o numerze c[i] z przedziału a[i]..b[i], przy czym 1 ≤ a[i] ≤ c[i] ≤ b[i] ≤ N. Mając dane tablice a[] i b[] wyznacz dopuszczalne położenie pionków (załóż, że zawsze takie istnieje).
Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; 1 ≤ a[i] ≤ b[i] ≤ N
Wejście: N a[1] b[1] a[2] b[2] ... a[N] b[N] {4 2 2 1 3 1 2 2 4}
Wyjście: c[1] c[2] ... c[N] {2 3 1 4}
Uwaga! Zadanie da się rozwiązać w czasie O(N*log*N) na lasach zbiorów rozłącznych (FIND-UNION). Tutaj takiego rozwiązania nie wymagamy, ale polecamy pomyśleć nad nim.
Zadanie C10 - najdłuższy malejący podciąg O(N*logN)Mamy ciąg N liczb całkowitych A[i]. Wyznacz długość najdłuższego (nie koniecznie spójnego) podciągu ściśle malejącego.
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ A[i] ≤ 10.000
Wejście: N A[1] A[2] ... A[N] {6 6 4 5 3 7 2}
Wyjście: długość_najdłuższego_ciągu {4}