Zadania - zestaw A

Zadanie A1 - czy można zbudować trójkąty? O(N)

Mamy danych N odcinków o długościach p_i/q_i. Czy z wszystkich trójek tych odcinków da się zbudować trójkąt o niezerowym polu?

Dane: 3 ≤ N ≤ 20.000; 1 ≤ i ≤ N; 1 ≤ p_i, q_i ≤ 1.000
Wejście: N p₁ q₁ p₂ q₂ ... p_N q_N {4 2 1 3 3 6 4 1 2}
Wyjście: TAK/NIE {NIE}

Zadanie A2a - sklejanie równych obiektów

Mamy następujące reguły konstrukcji obiektów: (1) mamy do dyspozycji od razu nieskończenie wiele kwadratów 1x1; (2) nowy obiekt można uzyskać z dwóch innych przez sklejenie ich wzdłuż krawędzi o równej długości; (3) sklejane obiekty muszą mieć równe pole. Mamy daną liczbę S. Wyznaczyć liczbę wszystkich obiektów, z dokładnością do izometrii (obrotów i przesunięć), o polu nie większym niż S.

Dane: 1 ≤ S ≤ 10.000
Wejście: S
Wyjście: liczba_obiektów

Zadanie A2b - sklejanie obiektów

W tej wersji zadania sklejane obiekty nie muszą mieć równego pola, tj. odpada reguła (3).

Dane: 1 ≤ S ≤ 10.000
Wejście: S
Wyjście: liczba_obiektów

Zadanie A3 - osobistości O(N)

Mamy N osób. Osobistość to osoba, którą wszyscy znają, a która nie zna nikogo oprócz siebie. Element Zna[A,B] (typu logicznego) mówi czy osoba A zna osobę B. Znaleźć liczbę osobistości.

Dane: 1 ≤ N ≤ 100; 1 ≤ i, j ≤ N; Zna[i,j] ∈ {TAK,NIE}
Wejście: N Zna[1,1] Zna[1,2] ... Zna[1,N] Zna[2,1] ... Zna[2,N] ..... Zna[N,1] ... Zna[N,N] {2 TAK TAK NIE TAK}
Wyjście: liczba_osobistości {1}

Zadanie A4 - wyszukiwanie w macierzy O(N)

Mamy tablicę dwuwymiarową T[1..N,1..N] ściśle posortowaną zarówno wierszowo (T[i,j] < T[i,j+1]), jak i kolumnowo (T[i,j] < T[i+1,j]). Znaleźć liczbę wystąpień wartości K w tej tablicy.

Dane: 1 ≤ N ≤ 50; 0 ≤ K ≤ 10⁹; 1 ≤ i, j ≤ N; 0 ≤ T[i,j] ≤ 10⁹
Wejście: N K T[1,1] T[1,2] ... T[1,N] T[2,1] ... T[2,N] ..... T[N,1] ... T[N,N] {2 3 1 3 3 4}
Wyjście: liczba_wystąpień_K {2}

Zadanie A5 - wyszukiwanie z indeksem O(logN)

Mamy dany ściśle posortowany wektor liczb całkowitych A[1..N] (A[i] < A[i+1]). Znaleźć najmniejsze takie k, że A[k] = k, bądź wypisać, że nie istnieje.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; –20.000 ≤ A[i] ≤ 20.000
Wejście: N A[1] A[2] ... A[N] {4 0 2 3 5}
Wyjście: wartość_k lub NIE {2}

Zadanie A6 - wyszukiwanie dodatkowego elementu O(logN)

Dane są dwie ściśle posortowane (<) tablice: A[1..N], B[1..N+1], przy czym B zawiera wszystkie elementy A i jeszcze jeden dodatkowy. Znaleźć go.

Dane: 1 ≤ N ≤ 5.000; 1 ≤ i ≤ N; 1 ≤ j ≤ N+1; 0 ≤ A[i], B[j] ≤ 20.000
Wejście: N A[1] A[2] ... A[N] B[1] B[2] ... B[N] B[N+1] {3 0 5 8 0 4 5 8}
Wyjście: dodatkowy_element {4}

Zadanie A7 - przydział laboratoriów O(N+K)

Program komputerowy realizuje następujące zlecenia. Od każdego z K pracowników instytutu przyjmuje deklarację, kiedy dany pracownik, chce prowadzić badania. Pracownik informuje program o chęci wykorzystania laboratorium w jednostkach czasu od a do b, ale bez b (a i b są całkowite) wywołując funkcję ALLOC(a,b), gdzie 0 ≤ a < b ≤ N. Na końcu operator wywołuje funkcję PRINT, która dla poszczególnych jednostek czasu j wypisuje liczbę pracowników chętnych na nią P[j]. Podaj propozycję efektywnej implementacji obu funkcji przyjmując, że K jest w przybliżeniu równe N.

Dane: 1 ≤ N, K ≤ 10.000; 1 ≤ i ≤ K; 0 ≤ a_i < b_i ≤ N
Wejście: K N a₁ b₁ a₂ b₂ ... a_K b_K {2 4 2 4 1 3}
Wyjście: P[0] P[1] ... P[N-1] {0 1 2 1}

Zadanie A8 - pary o danej sumie O(N*logN)

W podanym ciągu N różnych liczb A[1..N] znajdź liczbę par nieuporządkowanych (i,j), takich że A[i] + A[j] = S.

Dane: 1 ≤ N ≤ 10.000; 1 ≤ i ≤ N; 0 ≤ A[i], S ≤ 10⁹
Wejście: N S A[1] A[2] ... A[N] {4 5 4 2 1 3}
Wyjście: liczba_par {2}

Zadanie A9 - permutacja antyarytmetyczna O(N*logN)

Permutację (A[1],A[2],...,A[N]) ciągu (1,2,...,N) nazywamy antyarytmetyczną, jeśli liczby żadnego ciągu arytmetycznego o długości 3 nie występują we właściwej kolejności. Np. ciąg (1,5,3,2,6,4) jest permutacją antyarytmetyczną, a ciąg (6,1,5,4,3,2) nie jest ze względu np. na (6,4,2). Dla danej liczby N wypisać dowolną permutację antyarytmetyczną ciągu (1,2,...,N).

Dane:1 ≤ N ≤ 250.000
Wejście: N {5}
Wyjście: A[1] A[2] ... A[N] {1 5 3 4 2}

Wskazówka! Najpierw pomyśl nad rozbiciem liczb z zakresu 1..N na parzyste i nieparzyste, a później nieco to uogólnij.

Zadanie A10 - notacja O(.)

Uporządkuj poniższe funkcje niemalejąco ze względu na notację O(.) (tj. używając relacji < oraz =):

1: log(log^*(n))	2: 2log^(n)	3: (sqrt(2))^log2(n)	4: n²	5: n!	6: (log₂(n))!
7: (3/2)ⁿ	8: n³	9: log²n	10: log(n!)	11: 2^(2ⁿ)	12: n^1/log2(n)
13: ln(ln(n))	14: log^*(n)	15: n*2ⁿ	16: n^{log2(log2(n))}	17: ln(n)	18: 1
19: 2^log2(n)	20: (log2(n))^log2(n)	21: eⁿ	22: 4^log2(n)	23: (n+1)!	24: sqrt(log(n))
25: log^*(log(n))	26: sqrt(n)	27: n	28: 2ⁿ	29: n*log(n)	30: 2^(2ⁿ⁺¹)

Definicja funkcji log^*(x):
log^*(x) = 0, dla x ≤ 1
log^*(x) = log^*(log₂(x))+1, dla x > 1
Czyli np. log^*(1) = 0, log^*(2) = 1, log^*(4=2²) = 2, log^*(16=2⁴) = 3, log^*(65536=2¹⁶) = 4, itd.

W celu prezentacji wyników należy napisać program, który dla podanego ciągu A[1..N] w/w funkcji wypisze je w niemalejącej kolejności wraz z relacjami jakie między nimi zachodzą (w przypadku relacji = należy wypisać funkcje w kolejności rosnących numerów). Zarówno na wejściu jak i na wyjściu należy posługiwać się numerami funkcji, a nie samymi funkcjami.

Dane: 1 ≤ N ≤ 30; 1 ≤ i ≤ N; 1 ≤ A[i] ≤ 30
Wejście: N A[1] A[2] ... A[N] {4 27 23 19 14}
Wyjście: posortowany_ciąg_A (bez odstępów!) {14<19=27<23}

Uwaga! Program powinien mieć stablicowane relacje między funkcjami, a nie próbować je wyliczać numerycznie.