Задание 26 ЕГЭ по информатике · B1F57A
Коробки и коржи: вложение с заданной разностьюПовышеннаяКЭС 3.10
В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и так далее. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 11 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число N — количество коробок в магазине, не превышающее 10 000. В следующих N строках находятся значения длин сторон коробок, каждое в отдельной строке. Все числа натуральные и не превышают 10 000.
Для выполнения задания используйте данные из прилагаемого файла.
1_B1F57A.zipВ первой строке входного файла находится число N — количество коробок в магазине, не превышающее 10 000. В следующих N строках находятся значения длин сторон коробок, каждое в отдельной строке. Все числа натуральные и не превышают 10 000.
Для выполнения задания используйте данные из прилагаемого файла.
Показать ответ
854 54
Подсказки (3)
- В каком порядке удобнее рассматривать длины сторон коробок, чтобы строить цепочку вложений?
- Отсортируйте размеры по возрастанию. Следующую коробку можно выбрать, если её сторона не меньше текущей стороны плюс 11.
- Для каждой возможной первой коробки найдите максимальную цепочку жадным проходом по отсортированному массиву. Среди цепочек максимальной длины выберите ту, у которой первая сторона больше.
Решение
1. Считаем размеры коробок из файла и сортируем их по возрастанию. Одинаковые размеры сохраняем, поскольку коробки являются отдельными предметами.
a1≤a2≤⋯≤aN
2. Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.
aj−ai≥11
3. Жадный выбор самой ранней подходящей коробки оставляет максимально возможный запас для продолжения цепочки, поэтому даёт максимальную длину цепочки для выбранной первой коробки.
next≥current+11
4. Перебираем все возможные начальные коробки и сравниваем полученные длины цепочек. Если длина совпадает, сохраняем большую сторону начальной коробки.
5. После обработки файла выводим максимальное количество коробок и максимальный размер самой маленькой коробки через пробел.
a1≤a2≤⋯≤aN
2. Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.
aj−ai≥11
3. Жадный выбор самой ранней подходящей коробки оставляет максимально возможный запас для продолжения цепочки, поэтому даёт максимальную длину цепочки для выбранной первой коробки.
next≥current+11
4. Перебираем все возможные начальные коробки и сравниваем полученные длины цепочек. Если длина совпадает, сохраняем большую сторону начальной коробки.
5. После обработки файла выводим максимальное количество коробок и максимальный размер самой маленькой коробки через пробел.
Частые ошибки
- Считать, что разность размеров должна быть ровно 11, хотя она должна быть не меньше 11.
- Удалять повторяющиеся размеры коробок.
- При одинаковой длине цепочки выбирать меньшую первую коробку.
- Выводить размеры коробок вместо количества коробок и размера самой маленькой коробки.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 38235A26В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на…Коробки и коржи: вложение с заданной разностью · 553F8026В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина…Коробки и коржи: вложение с заданной разностью · 8091A926В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых…Коробки и коржи: вложение с заданной разностью · CBF8FC26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 028618
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.