A

Итак, в этой задаче можно было просто выполнить то, что было написано в условии – перебрать все числа от A до B, для каждого из них перебрать все перестановки модулей и проверить, что не менее чем для 7 перестановок f(x)=x.

А еще можно было заметить следующее. Пусть p=min(p1,p2,p3,p4). Тогда если x<p, то, очевидно, при взятии любого модуля x не изменится, ведь он меньше любого модуля. Очевидно также, что в противному случае он изменится, потому что будет взят по определенному модулю, меньше или равному х. Таким образом, вне зависимости от перестановки модулей, для числа либо выполняется равенство f(x)=x, либо не выполняется. Некоторые участники просто проверили для определенной перестановки модулей, подходит ли каждое число из промежутка, и вывели количество чисел, для которых равенство выполняется. Однако достаточно было даже просто посчитать количество чисел в пересечении интервалов [0;p-1] и [a;b].

B

Пусть у нас после всех перераспределений энергии во всех накопителях установился уровень энергии, равный Х. Тогда очевидно, что все накопители, в которых было больше Х изначально, должны передавать энергию накопителям, в которых изначально было меньше Х. Таким образом, каждая частица энергии будет передана лишь один раз. Пусть изначально у всех накопителей, у которых было больше Х энергии, в сумме было Up, а всего их было A, а у остальных сумма – Dn, и их B=N-A. Тогда (Up-A*X)*(100-K)/100.0= X*B-Dn – то, что нужно заполнить, составляет 100-К процентов от того, что надо убрать. Ясно, что одна из сторон этого равенства будет возрастать, а вторая – падать, при изменении Х. Следовательно, можно реализовать двоичный поиск по величине Х, подсчитать левую и правую часть этого уравнения, и изменять границы в зависимости от того, какая часть больше.

На самом деле можно перебирать Х, равный только величине начальной энергии в какой-то точке, это можно сделать в целых числах, а затем на фиксированном промежутке между двумя значениями найти ответ аналитически. Любопытные могут вывести формулы самостоятельно.

C

            Авторы предполагали следующее решение задачи: последовательно перебираем количество топлива, которое течет по каждой трубе. В тот момент, когда значения топлива во всех трубах, идущих от или к какой-то вершине, уже определены, (если это не начальная и не конечная вершина) проверяем, что сумма топлива, которое втекло в узел, равна сумме топлива, которое из него вытекла.  Также надо было проверять, что сумма топлива, текущего из начальной вершины, не больше уже найденного лучшего ответа. Решение работает в пределах 30мс на всех тестах.

            Хотелось бы услышать, какое решение писали некоторые участники. Напоминает динамику по профилю?

 UPD: Оценка сложности. Ребер из первой вершины 5. Перебор всех возможных значений потока в этих ребрах - 6⁵ Из каждой следующей на 1 ребро меньше, но надо учесть, что значение потока по последнему ребру определяется однозначно. Стало быть сложность 6⁵ * 6³ * 6² * 6¹ * 6⁰ * 6 = 6¹² = 2176782336. Последний множитель - это проверка на то, что сумма входящих равна сумме выходящих. Это число велико, но участники сами могли убедиться, что при отсечении, что мы не рассматривает поток больший уже найденного, решение работает очень быстро.

E

Disclaimer: Я буду часто употреблять фразу «треугольник», подразумевая «точки, соотвествующие данному треугольнику».

Во-1, очевидно, что если два треугольника полностью совпадают, то имеет смысл их наложить.

Теперь предположим, что у нас нету полностью совпадающих треугольников.

Посмотрим на лучшее возможное расположение треугольников на плоскости, такое, что оно состоит ровно из оптимального числа точек.

Рассмотрим граф из 4 вершин, соответствующих треугольникам. Между парой вершин столько ребер, сколько общих точек у двух соответствующих треугольников.

Ясно, что этот граф связен. ( Пусть это не так. Тогда у нас есть два множества треугольников, не имеющие общих точек. Сдвинем одно множество так, чтобы у него была общая точка со вторым множеством. Ответ уменьшился. Противоречие. )

Посмотрим на графы в этом цикле.

Что значит, что есть цикл длины 2? Значит, у 2 треугольников две общие точки.

Что значит, что есть цикл длины 3? Значит, есть тройка точек, таких, что любые две принадлежат какому-то из трёх треугольников.

Что значит, что есть цикл длины 4 и нету циклов длины 2 и 3? Это значит, что есть 4 точки, такие, что любые две соседних принадлежат какому-то треугольнику. Этот случай можно рассмотреть отдельно – проверить, что можно выбрать по стороне от каждого из треугольников так, чтобы они образовывали 4угольник. Пускай мы его рассмотрели.

Итак, как мы можем перебрать все разумные расположения точек? Будем перебирать все порядки добавления треугольников. Пусть у нас уже добавлены некоторые точки. Может произойти одно из трех действий:

1). Мы просто добавляем наш очередной треугольник так, чтобы он имел общую точку со всеми предыдущими. К примеру, одна точка в (0,0), еще одна в (х,0), еще одна со строго положительной ординатой.

2). Мы нашли пару точек, расстояние между которыми равно стороне текущего треугольника. Тогда у нас есть не более 4 вариантов, как приставить его, чтобы его сторона совпала с отрезком, соединяющим две выбранные точки. Добавили, пошли дальше.

3). Мы нашли пару точек A B, таких, что можно найти такую точку С, что расстояния АВ и АС равны сторонам двух еще не добавленных треугольников соответственно. Добавляем эти два треугольника. Это соответствует либо циклу длины 3, либо 4 либо какому-то пути.

Проверяем что число точек в данный момент не превышает оптимального, переходим к следующему ( в случаях 1-2) или через 1 (в случае 3) треугольнику. И все)

Деталь реализации: чтобы найти точку, находящуюся на двух заданных расстояниях от двух заданных точек, достаточно уметь пересекать окружности.