Algoritmizace – 5. 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.