Zadania - zestaw D1

Zadanie D11 - wybór wierzchołków drzewa O(N)

W danym N-wierzchołkowym drzewie wyznaczyć taki najmniejszy zbiór wierzchołków, że każdy inny wierzchołek jest styczny krawędzią z jakimś z tego zbioru. Wierzchołki drzewa są ponumerowane od 1 do N, a drzewo jest jednoznacznie wyznaczone przez numery ojców poszczególnych wierzchołków P[v]. Gdy wierzchołek jest korzeniem (nie ma ojca), to P[v] = 0.

Dane: 1 ≤ N ≤ 5.000; 1 ≤ v ≤ N; 0 ≤ P[v] ≤ N
Wejście: N P[1] P[2] ... P[N] {5 0 1 2 2 2}
Wyjście: liczba_wierzchołków {1}

Zadanie D12 - średnica drzewa O(N)

Mamy dane N-wierzchołkowe drzewo (zdefiniowane tak jak w poprzednim zadaniu). Wyznacz średnicę drzewa, tj. odległość pomiędzy dwoma najbardziej oddalonymi od siebie wierzchołkami.

Dane: 1 ≤ N ≤ 5.000; 1 ≤ v ≤ N; 0 ≤ P[v] ≤ N
Wejście: N P[1] P[2] ... P[N] {8 0 1 2 2 4 5 3 2}
Wyjście: średnica_drzewa {5}

Zadanie D13 - towarzyskość

W pewnej firmie, w której struktura zatrudnienia ma strukturę drzewiastą organizuje się przyjęcie. Nie jest jednak wskazane, aby na przyjęcie był zapraszany jednocześnie podwładny i jego bezpośredni zwierzchnik. Każda osoba ma współczynnik towarzyskości T[i]. Chodzi o to, aby zaprosić na przyjęcie takie osoby, by ich sumaryczny współczynnik towarzyskości był jak największy. Format drzewa jak w poprzednich zadaniach.

Dane: 1 ≤ N ≤ 5.000; 1 ≤ v ≤ N; 0 ≤ P[v] ≤ N; 0 ≤ T[v] ≤ 10.000
Wejście: N P[1] P[2] ... P[N] T[1] T[2] ... T[N] {4 0 1 2 2 3 5 2 1}
Wyjście: współczynnik_towarzyskości {6}

Zadanie D14a - składanie sumy pieniędzy O(N*S)

Mamy banknoty o całkowitych nominałach A[1],...,A[N]. Trzeba określić w jak najmniejszej liczbie banknotów można wydać daną sumę pieniędzy S lub stwierdzić, że to niemożliwe. Mamy do dyspozycji nieograniczoną liczbę banknotów każdego rodzaju.

Dane: 1 ≤ N ≤ 100; 1 ≤ S ≤ 1.000
Wejście: N S A[1] A[2] ... A[N] {4 10 1 2 3 4}
Wyjście: liczba_banknotów lub NIE {3}

Zadanie D14b - składanie sumy pieniędzy mając 1 banknot z rodzaju O(N*S)

Jak w poprzedniej wersji zadania, ale tym razem mamy do dyspozycji tylko jeden banknot każdego rodzaju.

Dane: 1 ≤ N ≤ 100; 1 ≤ S ≤ 1.000
Wejście: N S A[1] A[2] ... A[N] {4 10 1 2 3 4}
Wyjście: liczba_banknotów lub NIE {4}

Zadanie D15 - rozcinanie prostokąta O(N*M*(N+M))

Mamy do dyspozycji maszynę, która daną prostokątną płytę może przeciąć równolegle do jednego z boków. Otrzymane prostokąty możemy ciąć dalej w ten sam sposób (niezależnie od siebie). Należy wyznaczyć minimalną liczbę cięć konieczną do otrzymania samych kwadratów. Początkowy prostokąt ma wymiary N na M.

Dane: 1 ≤ N, M ≤ 100
Wejście: N M {6 5}
Wyjście: minimalna_liczba_cięć {4}

Zadanie D16 - schemat binarny O(N)

Schematem binarnym nazywamy skończony ciąg symboli ∈{'0','1','?'}. Dana liczba binarna jest zgodna ze schematem, jeśli na wszystkich miejscach, gdzie w schemacie nie występuje '?' cyfry liczby i schematu są takie same (np. "0110" jest zgodna z "0?1?"). Ile liczb z przedziału domkniętego <a;b> jest zgodnych ze schematem? Liczby a i b są podane w układzie dwójkowym. Można przyjąć, że długość schematu binarnego i binarnych reprezentacji a i b są równe N.

Dane: 1 ≤ N ≤ 1.000; 1 ≤ a ≤ b < 2N; b–a < 109
Wejście: N schemat a b {4 01?1 0010 1111}
Wyjście: liczba_liczb_zgodnych_ze_schematem {2}

Wskazówka! <a;b> = <0;b+1) \ <0;a).

Zadanie D17 - 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! Prosimy o algorytm programowania dynamicznego.

Zadanie D18 - optymalna triangulacja O(N3)

Dla danego N-wierzchołkowego wielokąta wypukłego wybrać taką triangulację zupełną (tj. rozdział na trójkąty), że suma długości wszystkich odcinków jest jak najmniejsza. Odcinki obwodu się także liczą. Wielokąt jest dany przez rzeczywiste współrzędne punktów (xi,yi), w porządku zgodnym z ruchem wskazówek zegara. Wynik podaj z dokładnością do 2 miejsc po przecinku.

Dane: 1 ≤ N ≤ 100; -105 ≤ xi, yi  ≤ 105
Wejście: N x1 y1 x2 y2 ... xN yN {4 0 0 0 3 1 2 1 1}
Wyjście: suma_długości_odcinków {8.53}

Zadanie D19 - nie za gęste zbiory O(N)

Wyznaczyć liczbę podzbiorów zbioru {1,2,...,N}, który z każdej trójki kolejnych liczb naturalnych zawiera co najwyżej jedną liczbę (czyli zbiór {1,4} jest dobry, natomiast {2,4} już nie). Ponieważ liczba ta rośnie wykładniczo wystarczy podać cztery ostatnie cyfry (a dokładniej, resztę modulo 10.000).

Dane: 1 ≤ N ≤ 10.000
Wejście: N {7}
Wyjście: liczba_zbiorów%10.000 {19}