Производство роботов

Автор задачи: Константин Бац, разработчик: Мария Жогова

Ограничения первой группы позволяли явно перебрать пары элементов. Для прохождения второй группы нужно было рассмотреть два случая: $$$a_i \bmod 100 < 50$$$ и $$$a_i \bmod 100 \geqslant 50$$$. Заметим, что в первом случае объединять производство в пары не имеет смысла, так как для таких роботов $$$\left\lfloor\frac{a_i + a_j}{100}\right\rfloor = \left\lfloor\frac{a_i}{100}\right\rfloor + \left\lfloor\frac{a_j}{100}\right\rfloor$$$. Во втором случае имеет смысл объединить в пары производство максимальное количество машин, так как каждое объединение будет дополнительно сохранять одну единицу ресурсов. Поскольку все $$$a_i$$$ равны, то объединять пары можно любым способом. Ясно, что можно получить не более $$$\left\lfloor\frac{n}{2}\right\rfloor$$$ пар.

В третьей подгруппе, аналогично, можно было разделить все затраты на производство на две группы: $$$a_i < 50$$$ и $$$a_i = 50$$$. Ясно, что производство из первой группы не имеет смысла объединять ни с производством из первой группы, ни с производством из второй группы — если $$$a_i < 50$$$, то $$$a_i + a_j \leqslant a_i + 50 < 100$$$, и это не сохранит ни одной единицы ресурсов. С другой стороны, имеет смысл объединить в пары как можно больше производств из второй группы, и каждое объединение даст одну единицу ресурсов. Таким образом, оптимальное распределение будет выглядеть так: $$$a_i < 50$$$ не объединяются ни с чем, $$$a_i = 50$$$ объединяются между собой.

Для полного решения необходимо заметить, что при формировании пар достаточно рассматривать не сами числа, а их остатки от деления на $$$100$$$, после чего объединять в пары остатки, дающие в сумме хотя бы $$$100$$$ (только в таком случае нам удастся сохранить дополнительную единицу ресурсов).

Давайте заменим все $$$a_i$$$ на $$$b_i = a_i \bmod 100$$$, и отсортируем эти остатки по неубыванию. Посмотрим, с чем можно объединить $$$b_1$$$:

Таким образом, достаточно двигаться двумя указателями $$$l$$$ и $$$r$$$ навстречу друг другу от самых маленьких ($$$l = 1$$$) и самых больших ($$$r = n$$$) остатков. Если $$$b_l + b_r \geqslant 100$$$, объединяем их в пару и сдвигаем указатели друг к другу — теперь можно повторить аналогичное рассуждение. Иначе, если $$$b_l$$$ не с чем объединять, сдвигаем только $$$l \to l + 1$$$. Время работы такого решения — $$$\mathcal{O}(n\log n)$$$ из-за сортировки.

Также заметим, что из-за того, что все остатки лежат от $$$0$$$ до $$$99$$$, можно обойтись без сортировки за $$$\mathcal{O}(n \log n)$$$, а просто посчитать количество $$$a_i$$$ с каждым отдельным остатком по модулю $$$100$$$ (сортировка подсчетом). Это бы дало время работы решения $$$\mathcal{O}(n)$$$, хотя и не было необходимо для получения полного балла.