Задание 26 ЕГЭ по информатике · CBF8FC
Коробки и коржи: вложение с заданной разностьюПовышеннаяКЭС 3.10
В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 4 единицы меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.
В первой строке входного файла находится число N — количество форм для коржей в кондитерской. В следующих N строках находятся значения диаметров форм для коржей, каждое — в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой форме.
Запишите два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем максимально возможный диаметр самого маленького коржа в таком торте.
Для выполнения задания используйте данные из прилагаемого входного файла.
1_CBF8FC.zipВ первой строке входного файла находится число N — количество форм для коржей в кондитерской. В следующих N строках находятся значения диаметров форм для коржей, каждое — в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой форме.
Запишите два целых числа: сначала наибольшее количество коржей, которое можно использовать для создания одного многоярусного торта, затем максимально возможный диаметр самого маленького коржа в таком торте.
Для выполнения задания используйте данные из прилагаемого входного файла.
Показать ответ
2172 50
Подсказки (3)
- Как упорядочить диаметры, чтобы последовательно выбирать коржи для ярусов?
- После сортировки по убыванию выбирайте следующий корж, если его диаметр не менее чем на 4 меньше диаметра предыдущего выбранного коржа.
- Переберите возможный самый маленький корж и найдите максимальную цепочку совместимых коржей. Среди цепочек максимальной длины выберите ту, у которой последний диаметр наибольший.
Решение
1. Сортируем все диаметры по убыванию. Для каждого выбранного коржа следующий можно взять только тогда, когда разность диаметров соседних выбранных коржей не меньше 4.
di−di+1≥4
2. Одним проходом по отсортированному массиву строим максимально длинную последовательность: берём очередной диаметр, если он удовлетворяет условию относительно последнего выбранного.
3. Число выбранных коржей является первым числом ответа. Последний выбранный диаметр — максимально возможный диаметр самого маленького коржа среди цепочек максимальной длины.
di−di+1≥4
2. Одним проходом по отсортированному массиву строим максимально длинную последовательность: берём очередной диаметр, если он удовлетворяет условию относительно последнего выбранного.
3. Число выбранных коржей является первым числом ответа. Последний выбранный диаметр — максимально возможный диаметр самого маленького коржа среди цепочек максимальной длины.
Частые ошибки
- Используют разность меньше 4 вместо условия не менее 4.
- Сортируют диаметры по возрастанию и неправильно интерпретируют порядок ярусов.
- Максимизируют диаметр самого маленького коржа, не обеспечив максимальное количество коржей.
- Учитывают только различные диаметры и теряют доступные формы одинакового диаметра.
Источник: Открытый банк ФИПИ
Похожие задания
26В магазине есть N кубических коробок. Одну коробку можно поместить в другую, если длина её стороны хотя бы на…Коробки и коржи: вложение с заданной разностью · 553F8026В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · 584C6A26В магазине для упаковки подарков есть N кубических коробок. Одну коробку можно поместить в другую, если длина…Коробки и коржи: вложение с заданной разностью · 8091A926В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по…Коробки и коржи: вложение с заданной разностью · B1F57A26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA6
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.