Автор задачи: Константин Бац, разработчик: Мария Жогова
Ограничения первой группы позволяли явно перебрать пары элементов. Для прохождения второй группы нужно было рассмотреть два случая: $$$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$$$:
Также заметим, что из-за того, что все остатки лежат от $$$0$$$ до $$$99$$$, можно обойтись без сортировки за $$$\mathcal{O}(n \log n)$$$, а просто посчитать количество $$$a_i$$$ с каждым отдельным остатком по модулю $$$100$$$ (сортировка подсчетом). Это бы дало время работы решения $$$\mathcal{O}(n)$$$, хотя и не было необходимо для получения полного балла.