1. Klasówka 2014/15#
Zadanie 1#
Mamy do wykonania \(n > 0\) zleceń. Dla każdego zlecenia znamy termin \(t\), do którego ma zostać ono wykonane oraz zysk z za jego wykonanie, jeśli zlecenie zostanie zrealizowane w terminie. Za zlecenie niezrealizowane w terminie zysk jest zerowy. Termin jest dodatnią liczbą całkowitą określającą numer dnia, do którego zlecenie ma być wykonane. Zyski są dodatnimi liczbami całkowitymi. Pierwszy dzień wykonywania zleceń ma numer \(1\). Jednego dnia można wykonać co najwyżej jedno zlecenie.
Zaproponuj efektywny algorytm, który obliczy kolejność wykonywania zleceń dającą największy sumaryczny zysk.
Wykonaj to samo, co w a) przy założeniu, że zysk z wykonania każdego zlecenia wynosi \(1\).
Zadanie 2#
Zaproponuj efektywną implementację kolejki lewicowej umożliwiającą wykonywanie klasycznych operacji \(Min\), \(DeleteMin\), \(Insert\) oraz nowej operacji \(AddAll(d)\) polegającej na dodaniu wartości \(d\) do wartości wszystkich kluczy aktualnie znajdujących się w kolejce.
Uwaga: Wartość \(d\) nie musi być fizycznie dodana do każdego klucza. Ważne, żeby wynikiem \(Min\) był zawsze klucz z aktualnie najmniejszą wartością, a \(DeleteMin\) usuwał właśnie taki klucz.
Zadanie 3#
Dane są liczby całkowite dodatnie \(n\), \(k\), przy czym \(k \le \sqrt{n}\). W tablicy \(a[1..n]\) zapisano \(n\) liczb całkowitych o co najmniej \(k\) różnych wartościach. Należy zaprojektować algorytm, który stabilnie i w miejscu przemieści \(k\) parami różnych liczb na początek tablicy \(a\) i uporządkuje je rosnąco. Stabilność w tym przypadku oznacza, że kolejność występowania w tablicy liczb o tych samych wartościach zostaje zachowana. Twój algorytm powinien działać w czasie \(O(n \log n)\)