Zadania - zestaw WA

Zadanie WA0 - Wyznaczanie maksimum O(N)

Mamy daną tablicę liczb całkowitych A[1..N]. Należy wyznaczyć maksimum.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i] ≤ 10⁹
Wejście: N A[1] A[2] ... A[N] {4 1 –1 2 1}
Wyjście: maksimum_z_A {2}

Zadanie WA1 - wyszukiwanie liniowe O(N)

Mamy daną tablicę liczb całkowitych A[1..N] oraz liczbę K. Należy stwierdzić, czy K występuje w tablicy A, tzn. czy istnieje takie j, że A[j] = K. Jeśli tak, to wypisujemy najmniejsze takie j, a jeśli nie to słowo NIE.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i], K ≤ 10⁹
Wejście: N K A[1] A[2] ... A[N] {4 7 1 –3 7 2}
Wyjście: indeks_j lub słowo NIE {3}

Zadanie WA2 - wyszukiwanie binarne O(logN)

Mamy daną ściśle posortowaną (<) tablicę liczb całkowitych A[1..N] oraz liczbę K. Należy stwierdzić, czy K występuje w tablicy A, tzn. czy istnieje takie j, że A[j] = K. Jeśli tak, to wypisujemy j, a jeśli nie to słowo NIE.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i], K ≤ 10⁹
Wejście: N K A[1] A[2] ... A[N] {5 7 –1 2 7 9}
Wyjście: indeks_j lub słowo NIE {3}

Zadanie WA3 - wyszukiwanie binarne z bajerkiem O(logN)

Tym razem daną normalnie posortowaną (≤) tablicę liczb całkowitych A[1..N] oraz liczbę K. Nie zwiększając złożoności wyszukiwania binarnego należy stwierdzić, ile razy K występuje w tablicy A.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i], K ≤ 10⁹
Wejście: N K A[1] A[2] ... A[N] {7 4 –1 –1 2 4 4 4 6}
Wyjście: liczba_wystąpień_K {3}

Zadanie WA4 - sortowanie przez wstawianie O(N²)

Mamy daną tablicę A[1..N]. Należy ją posortować (≤) algorytmem InsertionSort (sortowanie przez wstawianie). Tablica posortowana jest oznaczana jako B[1..N].

Dane: 1 ≤ N ≤ 1.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i] ≤ 10⁹
Wejście: N A[1] A[2] ... A[N] {4 2 5 –1 2}
Wyjście: B[1] B[2] ... B[N] {–1 2 2 5}

Zadanie WA5 - sortowanie przez wybieranie O(N²)

Mamy daną tablicę A[1..N]. Należy ją posortować (≤) algorytmem SelectionSort (sortowanie przez wybieranie w każdej iteracji najmniejszego elementu). Tablica posortowana jest oznaczana jako B[1..N].

Dane: 1 ≤ N ≤ 1.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i] ≤ 10⁹
Wejście: N A[1] A[2] ... A[N] {4 2 5 –1 2}
Wyjście: B[1] B[2] ... B[N] {–1 2 2 5}

Zadanie WA6 - sortowanie przez scalanie O(N*logN)

Mamy daną tablicę A[1..N]. Należy ją posortować (≤) algorytmem MergeSort (sortowanie przez scalanie posortowanych połówek). Tablica posortowana jest oznaczana jako B[1..N].

Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i] ≤ 10⁹
Wejście: N A[1] A[2] ... A[N] {4 2 5 –1 2}
Wyjście: B[1] B[2] ... B[N] {–1 2 2 5}

Zadanie WA7 - znajdowanie liczby inwersji O(N*logN)

Mamy daną tablicę A[1..N]. Inwersją nazywamy taką parę (niekoniecznie kolejnych) indeksów (i,j), że i < j, ale A[i] > A[j]. Np. tablica (1,3,4,2) ma 2 inwersje: (2,4) oraz (3,4). Zadanie polega na wyznaczeniu liczby inwersji w tablicy A.

Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; –10⁹ ≤ A[i] ≤ 10⁹
Wejście: N A[1] A[2] ... A[N] {4 2 4 3 1}
Wyjście: liczba_inwersji {4}

Wskazówka! Zmodyfikuj algorytm MergeSort tak, aby przy okazji sortowania wyznaczał liczbę inwersji.

Zadanie WA8 - generowanie wszystkich permutacji O(N!)

Należy wygenerować wszystkie permutacje ciągu (1, 2, ..., N) w dowolnym porządku. P_i,j oznacza j-ty wyraz i-tej permutacji.

Dane: 1 ≤ N ≤ 8
Wejście: N {3}
Wyjście: P_1,1 P_1,2 ... P_1,N P_2,1 P_2,2 ... P_2,N ..... P_N!,1 P_N!,2 ... P_N!,N {1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1}

Zadanie WA9 - wieża Hanoi O(2^N)

N krążków o różnych rozmiarach znajduje się na pierwszym palu (im wyżej tym mniejsze). Należy, zgodnie z regułami gry (tj. można przekładać jednocześnie po 1 krążku i nigdy krążek większy nie może leżeć na mniejszym), przemieścić je na drugi pal, wspierając się trzecim palem. Każdy ruch jest opisany za pomocą dwóch cyfr A_i oraz B_i i oznacza przeniesienie najwyższego krążka z pala A_i na pal B_i. Należy więc wyznaczyć odpowiedni ciąg 2^N–1 ruchów.

Dane: 1 ≤ N ≤ 10; k = 2^N–1
Wejście: N {3}
Wyjście: A₁ B₁ A₂ B₂ ... A_k B_k {1 2 1 3 2 3 1 2 3 1 3 2 1 2}

Zadanie WA10 - wieża Hanoi na czterech palach O(sqrt(N)*2^sqrt(N))

Zadanie jest bardzo podobne do poprzedniego z tym wyjątkiem, że mamy do dyspozycji cztery pale, a nie, jak normalnie, trzy. Można więc słusznie przypuszczać iż w tym wypadku da się przełożyć wieżę wykonując mniejszą liczbę ruchów.

Dane: 1 ≤ N ≤ 128; k - liczba ruchów
Wejście: N {3}
Wyjście: A₁ B₁ A₂ B₂ ... A_k B_k {1 3 1 4 1 2 4 2 3 2}

Uwaga! Nie jest nam znany dowód optymalności żadnego rozwiązania tego zadania, więc nie mamy pewności, że nasze rozwiązanie jest optymalne. Akceptowane będą wszystkie rozwiązania, które dadzą wynik niegorszy od naszego i będą miały złożoność niegorszą od wyżej wymienionej.

Zadanie WA11 - podciąg spójny o największej sumie O(N)

Mamy daną tablicę liczb A[1..N]. Należy znaleźć takie indeksy i oraz j (1 ≤ i, j ≤ N), by suma podciągu A[i..j] była możliwie największa (gdy i > j to przyjmujemy, że ta suma jest równa 0). Nie potrzeba znajdować indeksów, wystarczy znaleźć maksymalną sumę.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ k ≤ N; –10.000 ≤ A[k] ≤ 10.000
Wejście: N A[1] A[2] ... A[N] {5 2 –3 4 –3 4}
Wyjście: maksymalna_suma {5}

Uwaga! Jeśli możesz, spróbuj wymyślić algorytm wykorzystujący ciąg sum częściowych.

Zadanie WA12 - prostokąt o największej sumie O(N³)

Mamy daną dwuwymiarową tablicę liczb A[1..N,1..N]. Należy znaleźć taki podprostokąt (być może pusty, a być może będący całą tablicą), że suma liczb, które obejmuje jest jak największa. Wystarczy wypisać sumę.

Dane: 1 ≤ N ≤ 100; 1 ≤ i, j ≤ N; –10.000 ≤ A[i,j] ≤ 10.000
Wejście: N A[1,1] A[1,2] ... A[1,N] A[2,1] ... A[2,N] ..... A[N,1] ... A[N,N] {3 –1 2 1 2 2 0 0 2 –9}
Wyjście: maksymalna_suma {7}

Zadanie WA13 - największy pusty prostokąt na bitmapie O(N²)

Mamy daną dwuwymiarową bitmapę A[1..N,1..N], której pola są równe 0 lub 1. Należy znaleźć podprostokąt tej bitmapy o największym polu, taki że wszystkie jego pola będą równe 0.

Dane: 1 ≤ N ≤ 100; 1 ≤ i, j ≤ N; A[i,j] ∈ {0,1}
Wejście: N A[1,1] A[1,2] ... A[1,N] A[2,1] ... A[2,N] ..... A[N,1] ... A[N,N] {3 1 0 1 0 0 0 1 0 0}
Wyjście: maksymalne_pole (4)