Изменения
Нет описания правки
# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний на чашечных весах: по одной гирьке на каждой чаше. Известны результаты этих взвешиваний. Определите какой-нибудь порядок гирек, который не противоречит результатам взвешивания за $O(n + m)$.
# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний по порядку на чашечных весах: по одной гирьке на каждой чаше. Известны возможные результаты этих взвешиваний, возможно, некоторые из них некорректные. Определите, после какого из взвешиваний, полученная информация стала противоречивой за $O((n + m) \log n)$.
# У вас есть $n$ дел, а также некоторые дела зависят от других: их нельзя сделать раньше тех, от которых зависят. Граф зависимостей дел не имеет циклов. Каждое дело занимает у вас один час. Известно дело под номером $x$, которое является очень важным. Определите порядок выполнения всех дел, чтобы то, которое под номером $x$, было выполнено как можно раньше за линейное от входных данных время.
# Предложите алгоритм, который находит лексикографически минимальную топологическую сортировку за $O((V + E) \log V)$.
# Предложите алгоритм, который находит топологическую сортировку, у которой обратная перестановка минимальна лексикографически за $O((E + V) \log V)$.
