Algoritmizace – 6. cvičení

Počet jedniček

Mějme posloupnost x_1, \dots, x_n, kde x_i \in \{ 0, 1 \}. Dostaneme k dotazů tvaru (a, b) a máme odpovědět, kolik jedniček je v úseku x_a, \dots, x_b.

Úsek se zadaným součtem

Mějme posloupnost x_1, \dots, x_n, kde x_i > 0. Najděte souvislý úsek se součtem přesně S.

Příklad:

5, 3, 6, 3, 1, 2, 4.

S = 10.

Hledaný úsek může výt třeba 6, 3, 1.

Nejdelší vyvážený úsek

Mějme posloupnost x_1, \dots, x_n, kde x_i \in \{ -1, 1 \} (můžeme také používat značení -, +). Hledáme nejdelší úsek se součtem 0.

Příklad:

+, +, +, -, -, +, +, +, -, +, -, -, +.

Hledaný úsek může výt třeba vše od prvního - do konce.