Dany jest ciąg A operacji na stogu (INSERT x - wkłada wartość x na stóg; DELMIN - podaje i usuwa najmniejszą wartość ze stogu). Należy znaleźć kolejne wartości zwracane przez operację DELMIN.
Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; A[i] ∈ {INSERT xi, DELMIN}; –109 ≤ xi ≤ 109
Wejście: N A[1] A[2] ... A[N] {5 INSERT 2 INSERT 1 DELMIN INSERT 3 DELMIN}
Wyjście: ciąg_wyników_DELMIN {1 2}
Uwaga! Preferowany jest algorytm on-line, tj. taki, który podczas obsługi danej operacji nie wie jakie operacje nastąpią później.
Zadanie WB2 - sumowanie przedziałów off-line O(N+K)Dany jest ciąg przedziałów domkniętych <ai;bi>, gdzie ai, bi ∈ <1;K>. Z każdym przedziałem związana jest waga wi. Należy napisać program, który dla każdej liczby całkowitej x z zakresu <1;K> wypisze sumę wag W[x] przedziałów, które tę liczbę zawierają.
Dane: 1 ≤ N, K ≤ 4.000; 1 ≤ i ≤ N; 1 ≤ ai ≤ bi ≤ K; –10.000 ≤ wi ≤ 10.000
Wejście: N K a1 b1 w1 a2 b2 w2 ... aN bN wN {3 5 1 4 1 2 3 7 3 5 4}
Wyjście: W[1] W[2] ... W[K] {1 8 12 5 4}
[ Do zadania nie przygotowano jeszcze treści. Przepraszamy! ]
Zadanie WB4 - skalowanie liczb rzeczywistych O(N*logN)Mamy dany ciąg N różnych liczb rzeczywistych (xi). Naszym celem jest znalezienie bijekcji f tych liczb na zbiór liczb {1,2,...,N} zachowującej relację ≤. Innymi słowy najmniejszą z liczb xi zastępujemy przez 1, kolejną najmniejszą przez 2, itd.
Dane: 1 ≤ N ≤ 3.000; 1 ≤ i ≤ N; xi ∈ double
Wejście: N x1 x2 ... xN {5 0 5 3.14 2.7 1)
Wyjście: f(x1) f(x2) ... f(xN) (1 5 4 3 2)