Egzamin poprawkowy 2008/09

Zadanie 1

Słowa kluczowe: struktury danych, wzbogacanie

Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie ciągu następujących operacji na słowie zero-jedynkowym o długości \(n > 0\):

1. 1. \(Ini(<b_1, b_2, \cdots, b_n>) ::\) utwórz strukturę danych reprezentującą słowo \(b\); ta operacja jest wykonywana tylko raz, na samym początku.

   2. \(Zam(i: 1..n) :: b_i := 1 - b_i\).

   3. \(Blok(i: 1..n) ::\) podaj długość maksymalnego podsłowa \(<b_j,b_{j+1}, \cdots, b_k>\) złożonego z jednakowych symboli i takiego, że \(j \leq i \leq k\).

2. 1. \(Ini(<1, 1, \cdots, 1>) ::\) utwórz strukturę danych reprezentującą słowo \(b\) złożone z samych \(1\); ta operacja jest wykonywana tylko raz, na samym początku.

   2. \(Zam(i: 1..n) ::\) if \(b_i = 1\) then \(b_i := 1 - b_i\).

   3. \(Najblizsza(i: 1..n) ::\) podaj największą pozycję \(1\) w słowie \(b\) na lewo od \(b_i\); jeśli takiej pozycji nie ma, to wynikiem jest \(0\).

Zadanie 2

Słowa kluczowe: grafy

Grafem trójkątnym nazywamy graf spójny, w którym każda dwuspójna składowa jest trójkątem (cyklem długości \(3\)). Mamy dany graf trójkątny reprezentowany przez listy sąsiedztwa. Zaprojektuj algorytm, który w czasie liniowym obliczy dla tego grafu liczbę różnych cykli Eulera modulo \(2009\). Przyjmujemy, że każdy cykl Eulera jest zadawany przez ciąg kolejno odwiedzanych wierzchołków. Dwa ciągi takie same z dokładnością do przesunięcia cyklicznego definiują ten sam cykl.

Zadanie 3

Zaproponuj efektywny algorytm, który dla danej permutacji \(p = <p_1, p_2,\cdots, p_n>\) liczb \(1, 2, \cdots, n\) policzy liczbę malejących trójek \(<p_i, p_j, p_k>\), dla \(1 \leq i < j < k \leq n\).