Mamy dwie posortowane (≤) tablice A[1..N] oraz B[1..N]. Utwórzmy tablicę C[1..2*N] taką, że C[i] = A[i], C[N+i] = B[i] dla i=1..N. Niech D będzie posortowaną wersją tablicy C. Znaleźć element D[N]. (Nie chodzi tutaj o fizyczne tworzenie C i D - należy tylko podać wartość, która pojawiłaby się w D[N] gdyby jednak stworzyć te tablice.)
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –109 ≤ A[i], B[i] ≤ 109
Wejście: N A[1] A[2] ... A[N] B[1] B[2] ... B[N] {3 1 2 4 3 5 6}
Wyjście: D[N] {3}
W pewnej wiosce mamy N domów położonych wzdłuż jednej ulicy. Domy stoją po kolei przy jezdni i są równoodległe od siebie. W i-tym domu mieszka A[i] członków jedynej partii. Wyznacz taką lokalizację domu partii, żeby suma długości dróg wszystkich członków do niego była jak najmniejsza (jeśli jest kilka możliwości, wybierz dom o najmniejszym numerze). W poszukiwaniu domu partii trzeba, z braku funduszy, ograniczyć się do już wybudowanych domów.
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ A[i] ≤ 10.000
Wejście: N A[1] A[2] ... A[N] {4 1 2 3 4}
Wyjście: nr_domu_partii {3}
Zadanie od poprzedniej wersji różni się tylko tym, że tym razem domy są od siebie w różnych odległościach. Dany jest dodatkowy ściśle rosnący wektor D[1..N] odległości domów od pierwszego domu.
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ A[i] ≤ 10.000;
0 ≤ D[i] ≤ 106;
D[1] = 0
Wejście: N A[1] A[2] ... A[N] D[1] D[2] ... D[N] {4 1 2 3 4 0 1 2 4}
Wyjście: nr_domu_partii {3}
Uwaga! Jeśli potrafisz, spóbuj nie używać typu całkowitego 64-bitowego. Zadanie da się rozwiązać, bez specjalnych kombinacji, na liczbach 32-bitowych.
Zadanie B3 - scalanie wielu ciągów O(N*K*logK)Mamy K posortowanych (≤) ciągów Aj[i], każdy o długości N. Scal je w jeden posortowany ciąg B[1..N*K].
Dane: 1 ≤ N*K ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ j ≤ K; –109 ≤ Aj[i] ≤ 109
Wejście: K N A1[1] A1[2] ... A1[N] A2[1] ... A2[N] ..... AK[1] ... AK[N] {2 2 1 4 2 3}
Wyjście: B[1] B[2] ... B[N*K] {1 2 3 4}
Zaprojektuj stosopodobną strukturę danych, na której, oprócz standardowych operacji PUSH i POP, można wykonywać jeszcze operację FINDMIN - wszystkie operacje powinny być wykonywane w czasie stałym O(1). Następnie zasymuluj jej działanie wykonując N danych operacji. Dla każdej operacji dającej wynik (tj. POP i FINDMIN) wypisz jej wynik na wyjściu.
Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; op[i] ∈ {PUSH liczba, POP, FINDMIN}
Wejście: N op[1] op[2] ... op[N] {5 PUSH 6 PUSH 5 FINDMIN POP FINDMIN}
Wyjście: ciąg_wyników_operacji {5 5 6}
W N-segmentowym magazynie stoi M beczek (w każdym segmencie co najwyżej 1). Beczka w segmencie i ma docelowy numer segmentu B[i] (z zakresu 1..N), w którym powinna się znaleźć (znów, dwie beczki nie mają tego samego adresu docelowego). Jeśli jednak B[i] = 0, oznacza to, że w i-tym segmencie nie stoi aktualnie żadna beczka. Możemy w czasie 1s przełożyć beczkę do pustego segmentu lub w czasie 2s zamienić beczki miejscami. Znajdź najkrótszy możliwy czas (w sekundach), w jakim można ustawić wszystkie beczki na swoich docelowych miejscach.
Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; 0 ≤ B[i] ≤ N
Wejście: N B[1] B[2] ... B[N] {6 2 3 4 0 6 5}
Wyjście: minimalny_czas {5}
Dla danych: całkowitego N i rzeczywistego x oblicz wartość wielomianu xn+xn-1+...+x2+x+1 używając tylko operacji +,-,* oraz dzielenia całkowitego przez 2. Wynik podaj z dokładnością do 4-tego miejsca po przecinku. Możesz założyć, że wynik mieści się w typie double.
Dane: 0 ≤ N ≤ 109; –2.000 ≤ x ≤ 2.000
Wejście: N x {3 1.5}
Wyjście: wartość_wielomianu {8.1250}
Mamy dany ciąg liczb A[1..N], który jest permutacją zbioru {1,2,...,N}. Dla każdego i znajdź liczbę B[i] takich j≤i, dla których A[j] ≤ A[i].
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ A[i] ≤ N
Wejście: N A[1] A[2] ... A[N] {4 1 3 4 2}
Wyjście: B[1] B[2] ... B[N] {1 2 3 2}
Uwaga! Prosimy o wymyślenie (i przysłanie) algorytmu opartego o odpowiednią strukturę danych. Najlepiej gdyby to był algorytm on-line, tj. licząc B[i] nie znał wartości A[j>i].
Zadanie B8 - odtwarzanie permutacji O(N*logN)Z wartości B[i] (z poprzedniego zadania) wylicz A[i].
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 1 ≤ B[i] ≤ N
Wejście: N B[1] B[2] ... B[N] {4 1 2 3 2}
Wyjście: A[1] A[2] ... A[N] {1 3 4 2}
Mamy N kobiet i N mężczyzn (numerowanych od 1 do N). Każda kobieta preferuje mężczyzn wedle ustalonej przez siebie kolejności i na odwrót. Listy preferencji oznaczamy przez K oraz M: i-ta kobieta najbardziej chciałaby być żoną mężczyzny o numerze K[i,1], później K[i,2] itd., a w ostateczności tego o numerze K[i,N]; podobnie dla mężczyzn. Znajdź takie połączenie w związki małżeńskie, że dla dowolnej kobiety i mężczyzny nie będących dla siebie żoną i mężem, albo ona preferuje bardziej swojego męża niż jego, albo on preferuje bardziej swoją żonę niż ją. Niech więc A[i] będzie numerem męża kobiety o numerze i.
Dane: 1 ≤ N ≤ 100; 1 ≤ i, j ≤ N; 1 ≤ K[i,j], M[i,j] ≤ N
Wejście: N K[1,1] ... K[1,N] ..... K[N,1] ... K[N,N] M[1,1] ... M[1,N] ..... M[N,1] ... M[N,N] {2 1 2 1 2 2 1 1 2}
Wyjście: A[1] A[2] ... A[N] {2 1}