Изменения
Нет описания правки
# Кузнечик прыгает по прямой в положительном направлении и всегда находится только в целых точках. Изначально он стоит в точке с координатой 1. Если кузнечик стоит в точке $x$, то он может прыгнуть в точки $x+1, x+2, \ldots, x+k$, где $k$ {{---}} максимальное число такое, что $x$ делится на $2^{k-1}$. Вам задано число $n$. Найдите число способов кузнечику добраться до точки $n$ за $O(\log^\alpha{n})$ для некоторого $\alpha$.
# Рассмотрим последовательность отрезков с целыми концами: $[l_1, r_2]$, $[l_2, r_2]$, $\ldots$, $[l_m, r_m]$ ($1 \le l_i \le r_i \le n$). Вам задан $x$ ($1 \le x \le n$), найдите число различных последовательностей отрезков, что никакой не вкладывается в другой и существует $i$, что $l_i=x$, за время $O((nm)^\frac{3}{2})$.
# Задано дерево из $n$ вершин. На каждом ребре записан один бит. Нам известно про каждое ребро, нужно ли оставить тот же бит или изменить на противоположный. На каждом шаге разрешается выбирать путь в дереве и изменять все биты на этом пути на противоположные. Какое минимальное число путей нужно выбрать, чтобы получить из начальной конфигурации битов конечную за $O(n^2)$.
</wikitex>
