Задача D.

Разобьем граф на компоненты связности (провинции). Далее будем рассматривать только граф на этих компонентах, то есть каждой провинции мы поставим в соответствие вершину нового графа. Пусть всего имеется n провинций. Изначально граф пустой, так как между провинциями дорог нет. При этом для каждой провинции мы имеем ограничение на число тоннелей, которые можно построить из этой провинции: k_i = min(k, c_i), где c_i – количество городов, изначально содержавшихся в провинции (компоненте) i. Полученный граф провинций требуется сделать связным за счет постройки тоннелей и дорог. При k = 1 получаем, что если после постройки дорог у нас осталось хотя бы 3 компоненты связности, то хотя бы из одной из них придется провести 2 тоннеля, что запрещено. Значит, нам надо будет провести хотя бы n – 2 дороги, чтобы осталось не более 2 компонент связности.

Далее будем считать, что k >= 2. Посчитаем, какое наибольшее количество тоннелей мы можем построить. Пусть s – сумма всех чисел k_i. Очевидно, мы не сможем построить больше, чем s / 2 тоннелей, поскольку каждый тоннель соединяет 2 провинции. Верно следующее утверждение: мы можем построить s / 2 (округление в нижнюю сторону) тоннелей или сделать граф связным, построив n – 1 тоннель (при s / 2 >= n – 1). Действительно, рассмотрим те вершины, для которых k_i > 1. Соединим эти вершины в цепочку тоннелями, а вершины для которых k_i = 1 будем присоединять к этой цепочке, пока возможно. Пусть мы провели менее s / 2 тоннелей и не можем провести еще один. Значит, у нас осталась ровно одна вершина j, степень которой не более, чем k_j – 2. Тогда получаем, что для этой вершины k_j > 1, то есть эта вершина принадлежит построенной цепочке, а все вершины, для которых k_i = 1, уже присоединены к этой цепочке (иначе бы мы смогли провести еще один тоннель), то есть граф связен.

Если, проведя s / 2 тоннелей, мы получили связный граф, то ответ 0. В противном случае граф будет состоять из n – s / 2 компонент связности, то есть нам потребуется провести еще хотя бы n – s / 2 – 1 дорогу. На самом деле такого количества дорог нам будет достаточно. Проведем n – s / 2 – 1 дорогу следующим образом. Выберем 2 различные компоненты связности (по дорогам или тоннелям) в текущем графе. Поскольку мы строили тоннели (и, возможно, дороги) только между различными компонентами связности, то каждая текущая компонента представляет собой дерево. Значит, в выбранных компонентах существуют вершины, степени которых не более 1. Выберем по одной такой вершине в каждой из выбранных компонент и соединим компоненты по этим вершинам (то есть вершины объединяем в одну, сохраняя ребра). Тем самым мы получили новую вершину (провинцию), из которой идет не более двух тоннелей, то есть мы не нарушили условия, поскольку k >= 2. Таким образом, мы сможем получить связный граф, построив дополнительно n – s / 2 – 1 дорогу, что и является ответом к задаче.

Задача E.

Если x = 2, то ответ 0. Далее будем считать, что x > 2.

Для того, чтобы однозначно определить искомое число предметов t мы должны выбрать множество чисел a_i, так чтобы для любого y от 2 до x представление y в режимах a_i было уникальным, т.е. множества чисел b(y,i) = y / ai (округленное вверх) были попарно различны между числами y. Заметим, что для каждого i функция b(y,i) монотонна по y. Значит, если для некоторого i для чисел y и z (y < z) выполняется b(y,i) = b(z,i), то выполняется и b(y,i) = b(y + 1,i). Тогда для выбора необходимого множества чисел a_i нам достаточно гарантировать для каждого y от 2 до x – 1 существование некоторого числа j, такого что b(y,j) < b(y + 1, j). Легко видеть, что b(y,j) < b(y + 1, j) тогда и только тогда, когда y делится без остатка на a_j. Таким образом, необходимо, чтобы для каждого y от 2 до x – 1 существовало такое a_i, что y делится на a_i. Если некоторое число a_i равно 1, то нам достаточно просмотреть список в этом режиме и ответ на задачу будет 1. В противном случае для выполнения условия нам необходимо и достаточно взять в множество просмотренных режимов все простые числа p_i < x. Действительно, если мы не использовали число p_i, то мы не сможем отличить числа p_i и (p_i + 1) (поскольку p_i не будет делиться ни на одно из выбранных чисел). Наоборот, если мы взяли все простые числа меньшие x, то любое число от 2 до x - 1 будет делиться хотя бы на одно из них. Таким образом, нам необходимо проверить, встречаются ли все простые числа, меньшие x, среди a_i. Поскольку количество простых чисел от 1 до x есть величина порядка O(x / ln(x)), то при больших x все простые числа, меньшие x, не смогут оказаться в наборе чисел a_i. Например, верна оценка: при x > 20 * n, ответ будет -1. Значит, можно воспользоваться решетом Эратосфена для нахождения всех простых чисел, меньших x при x <= 20 * n и проверить, существует ли среди них число, не встречающееся среди a_i. Если такое число существует, то ответ к задаче -1, иначе ответом будет количество простых чисел меньших x.

Задача F.

Если для некоторой скорости v₁ мы смогли проехать из точки A в точку B, получив не более k попаданий, то для любой скорости v₂ >= v₁ мы так же сможем проехать из A в B. Значит, можно воспользоваться бинарным поиском для нахождения ответа.

Пусть мы зафиксировали скорость танка v. Необходимо посчитать, сколько танков сумеют выстрелить по нам в процессе езды. Рассмотрим вражеский танк i, находящийся в точке P плоскости. Он может пытаться прицелиться в наш танк двумя способами: повернуть башню на точку B или повернуть башню на точку A и затем поворачиваться от точки A к точке B. В первом случае достаточно сравнить время передвижения танка от A к B со временем поворота врага на точку B. Если вражеский танк сумеет прицелиться в точку B раньше, чем мы сумеем туда приехать, то он сможет сделать выстрел. Далее рассмотрим вторую возможную стратегию врага. Проведем перпендикуляр PQ к прямой AB. Разобьем отрезок AB на 2 части: AQ и QB (если Q не лежит на отрезке AB, то одна из частей будет пустой, а другая представляет собой отрезок AB – тогда за Q обозначим конец отрезка AB, ближайший к основанию перпендикуляра). Рассмотрим первую часть отрезка - AQ (до основания перпендикуляра). Легко проверить, что при постоянной угловой скорости поворота башни, линейная скорость прицела врага вдоль отрезка AB будет монотонно убывать. С учетом того, что скорость нашего танка вдоль AB постоянна, получаем, что функция разности координат прицела и танка на отрезке AQ от времени выпукла вниз (вторая производная отрицательна). Так же в этом можно убедиться, найдя вторую производную этой функции. Тогда мы можем воспользоваться троичным поиском для нахождения минимума этой функции на временном интервале, соответствующем преодолению танком отрезка AQ. Если в точке минимума функция отрицательна, то значит, враг смог прицелиться на наш танк и выстрелить. В противном случае, танк будет следовать впереди прицела на всём отрезке AQ. (Пользуясь аналогичными утверждениями, можно искать, например, минимум функции разности времен достижения некоторой точки D отрезка AQ прицелом врага и нашим танком). Можно избавиться от троичного поиска, найдя момент, когда скорости прицела и нашего танка сравняются, и проверить, кто будет ближе к точке B в этот момент. Но при этом необходимо аккуратно обработать случаи, когда одна скорость всегда больше другой на всём отрезке.

Далее рассмотрим вторую часть отрезка - QB (после основания перпендикуляра). Если враг не смог выстрелить в наш танк на первой части отрезка, то, стало быть, к моменту прицеливания врага на точку Q, наш танк будет находиться ближе к точке B, чем прицел. Аналогично первой части отрезка AB можно убедиться, что линейная скорость прицела вдоль QB будет монотонно возрастать. Пусть в какой-то момент времени прицел врага догнал танк в точке C отрезка QB. Тогда в этот момент скорость прицела должна быть выше скорости танка (иначе, танк догнать бы не удалось). В силу монотонности скорости прицела получаем, что и на оставшемся отрезке CB скорость прицела врага будет выше скорости танка, значит, прицел достигнет точки B раньше. Соответственно, если вражеский прицел достиг точки B позднее нашего танка, то танк находился впереди прицела и на всем отрезке QB. Таким образом, для определения возможности стрельбы врага нам достаточно проверить времена достижения точки B.

Проделав такие вычисления для каждого из n врагов, мы получим число попаданий по нашему танку и, сравнив это значение с числом k, перейдем в нужную ветку бинарного поиска скорости.