Изменения
Нет описания правки
# Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$.
# Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(2^n \cdot n)$.
# Заданы натуральные $S$, $L$ и $R$. Сколько есть чисел $x$ ($L \le x \le R$) таких, что сумма цифр $x$ равна $S$ за $O(\log^2 R)$.# Заданы три строки из цифр и знаков вопроса $a$, $b$ и $c$. Сколько существует троек чисел $x$, $y$ и $z$, таких, что $x$ получается из $a$ заменой знаков вопроса на цифры, $y$ из $b$ и $z$ из $c$ аналогичным способом, и $x+y=z$ за время $O(\log(\max(|a|, |b|, |c|))$.# Петя проводит $n$ независимых экспериментов, известны вероятности $p_i$ успешности $i$-го эксперимента. Посчитайте матожидание квадрата числа успешных событий за время $O(n^2)$.
</wikitex>
