Задание 26 ЕГЭ по информатике · 553F80
Коробки и коржи: вложение с заданной разностьюВысокаяКЭС 3.10
В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки в таком наборе. Размер подарка позволяет поместить его в самую маленькую коробку.
Во входном файле в первой строке указано число N, затем в N строках — длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки.
1_553F80.zipВо входном файле в первой строке указано число N, затем в N строках — длины сторон коробок. Запишите сначала наибольшее количество коробок, затем максимально возможную длину стороны самой маленькой коробки.
Показать ответ
2767 51
Подсказки (3)
- Как расположить длины сторон, чтобы последовательно проверять возможность вложения коробок?
- После сортировки по возрастанию поддерживайте длину текущей цепочки и размер её самой маленькой коробки.
- Если очередная сторона не меньше предыдущей выбранной стороны плюс 3, коробку можно добавить в цепочку. При одинаковой максимальной длине цепочки выбирайте цепочку с большей первой стороной.
Решение
1. Считаем все длины сторон коробок и сортируем их по возрастанию.
a1≤a2≤⋯≤aN
2. Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.
ai−alast≥3
3. Для каждой максимальной по длине цепочки запоминаем длину её первой коробки. Если длина цепочки увеличилась, заменяем ответ; если длина такая же, выбираем большую первую сторону.
4. Конкретные два числа определяются значениями из прилагаемого входного файла, содержимое которого в условии не приведено.
a1≤a2≤⋯≤aN
2. Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.
ai−alast≥3
3. Для каждой максимальной по длине цепочки запоминаем длину её первой коробки. Если длина цепочки увеличилась, заменяем ответ; если длина такая же, выбираем большую первую сторону.
4. Конкретные два числа определяются значениями из прилагаемого входного файла, содержимое которого в условии не приведено.
Частые ошибки
- Используют разность менее 3 между соседними коробками.
- Не сортируют длины сторон перед построением цепочки.
- При одинаковом максимальном количестве коробок выбирают не максимальную, а минимальную сторону самой маленькой коробки.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA626В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 0C143326В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 38235A26В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина…Коробки и коржи: вложение с заданной разностью · 8091A926В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · B1F57A26В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых…Коробки и коржи: вложение с заданной разностью · CBF8FC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.