Размещение симбиотов

Автор задачи и разработчик: Даниил Орешников

Заметим, что для размещения $$$n$$$ пар симбиотов потребуется хотя бы $$$2 \cdot \left\lceil \frac{n}{2}\right\rceil$$$ носителей. Это достигается (например) при условии, что симбиоты из нечетной пары $$$i$$$ размещаются в носителях из пары $$$i$$$, а симбиоты из четной пары $$$j$$$ размещаются в носителях из пары $$$j - 1$$$. В таком случае носители из четных рядов не потребуются и их можно будет отпустить. Очевидно, что использовать меньше носителей не получится, так как из условий размещения следует, что больше двух симбиотов в одном носителе не разместить.

Давайте решать задачу жадным образом, стремясь приблизить вид размещения к тому, которое приведено выше. Для этого поспользуемся следующим фактом: симбиотов, начиная с $$$i$$$-й пары, можно разместить, не затрагивая носителей из предыдущих пар. Поэтому, если при размещении $$$i$$$-й пары симбиотов есть возможность оставить носителя из $$$i-1$$$-й пары «свободным», следует это сделать. Действительно, если оптимальный ответ достигается заниманием этого носителя симбиотом, то где-то дальше есть свободный, до которого в каждой паре носителей размещен один симбиот с той же пары, и один — со следующей. В таком случае можно «сдвинуть» всех этих симбиотов вперед, освободив текущего, и не ухудшив ответ.

В первой паре симбиотов можно разместить любым способом, так как это ни на что не повлияет. Пусть мы уже разметили первые $$$i$$$ пар и сейчас размещаем $$$i + 1$$$-ю. Тогда

Следуя приведенным выше правилам, на каждом этапе мы будем получать размещение с максимальным числом неиспользованных носителей, а среди всех таких размещение с минимальной заполненностью носителей в последней паре. Ясно, что такое размещение в итоге приведет к размещению с минимальным количеством носителей, которого хватит для размещения всех симбиотов с соблюдением всех описанных условий.

Для решения достаточно последовательно рассмотреть каждую из $$$n$$$ пар симбиотов, постоянно поддерживая информацию о заполненности носителей в предыдущей паре. Пар носителей также $$$n$$$, поэтому время работы решения — $$$\mathcal{O}(n)$$$.