Карточки
Тесты
Главная
Курсы
Подписка
26. Прикладная задача: #298093
В магазине для упаковки подарков есть $N$ кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на $6$ единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Отсортируем длины сторон по возрастанию. Матрёшка — это цепочка, в которой каждая следующая коробка больше предыдущей хотя бы на $6$. Максимальную длину даёт обычная жадность: идём по возрастанию и берём коробку, если она подходит к последней взятой.
Со вторым вопросом жадность не справляется: она стартует с самой маленькой коробки, а нам нужна самая большая из возможных стартовых. Поэтому для каждой коробки считаем $ln[i]$ — длину максимальной цепочки, которая начинается именно с неё.
Работает удобное свойство: чем меньше коробка, тем длиннее цепочка от неё, потому что любую цепочку, начинающуюся с большей коробки, можно начать и с меньшей. Значит $ln$ не возрастает по мере роста стороны, и максимум среди подходящих продолжений достигается на самой первой коробке со стороной не менее $a_i + 6$. Её и находим двоичным поиском, а массив заполняем справа налево.
Затем берём $K$ — наибольшее значение в $ln$, и среди всех коробок с таким значением выбираем самую большую сторону.
from bisect import bisect_left
f = open('26-28.txt')
n = int(f.readline())
a = sorted(int(f.readline()) for _ in range(n))
ln = [1] * n # длина макс. цепочки, начинающейся с i-й коробки
for i in range(n-1, -1, -1):
j = bisect_left(a, a[i] + 6) # первая коробка, в которую влезет i-я
if j < n:
ln[i] = 1 + ln[j]
K = max(ln)
smallest = max(a[i] for i in range(n) if ln[i] == K)
print(K, smallest) # 1511 54
Проверка. В файле $10000$ коробок со сторонами от $50$ до $9998$, жадный подсчёт тоже даёт цепочку из $1511$ коробок. Стартовать можно с любой коробки от $50$ до $54$ — все дают ровно $1511$ звеньев, а со следующей уже только $1510$. Поэтому в ответ идёт наибольшая из подходящих, то есть $54$. На типовом примере из условия с разницей $3$ программа выдаёт $3$ и $32$.
20
