Вступление.
Задание 26 – самое нестандартное на ЕГЭ.
В отличие от других задач, у него нет заранее известной темы. Например, 24-я задача всегда связана с поиском подстроки, 25-я задача – задача про маски или делители, 27-я – про кластеризацию. Про 26ую задачу заранее известно только одно – она будет связана с сортировкой данных. Какой именно будет вопрос и каким способом искать ответ — заранее неизвестно. Из-за этого универсального алгоритма подготовки к ней не существует – задача проверяет общее понимание алгоритмов, умение анализировать условие и самостоятельно выстраивать решение.
Именно поэтому 26-ю можно считать одной из самых сложных в подготовке. Теоретически её можно усложнять бесконечно, и нельзя быть готовым ко всем вариантам. При этом важно понимать: на реальном ЕГЭ чаще всего 26-е задачи несложные. В прошлые годы большинство из них решались с помощью таблиц или простых алгоритмов, а программные версии были достаточно поверхностными. По-настоящему сложные варианты встречались крайне редко и чаще всего – на пересдачах и в резервные дни.
Задача №1 (2617)
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла 26.txt находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 100 000) и N – количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50
Решение
Задача заключается в том, чтобы определить два числа: наибольшее количество пользователей, чьи файлы можно поместить в архив, и максимальный размер файла, который может быть сохранен. Для того чтобы максимально эффективно использовать пространство, файлы сортируют по размеру, в порядке возрастания, потому что чем меньше объем файла, тем большее их количество поместится в хранилище.
Откроем файл в LibreCalc.
Размер свободного места на диске равен 8200, количество пользователей – 970. Переместим эти значения правее, а список значения объёмов файлов каждого пользователя отсортируем в порядке возрастания, потому что нам нужно сохранить как можно большее количество файлов. Столбец А озаглавим «Файлы»:
Дальше будем подсчитывать сколько места останется при добавлении очередного файла из списка, столбец В озаглавим «Сколько места останется», в ячейке B2 укажем число 8199 – после записи первого файла размером «1» свободное место на диске станет равным 8199. В ячейке B3 указываем формулу =B2-A2 и распространяем её до конца таблицы. Таким образом мы моделируем заполнение хранилища. Перейдем к первому отрицательному значению в столбце B – все файлы до строки с отрицательным значением поместятся на диск. Выделим строки с положительными значениями зеленым цветом и пронумеруем их в столбце С:
Видим, что на диске поместятся 568 файлов, это первое число для ответа на задачу.
первое число в ответе на задачу.
Второй вопрос задачи, какой максимальный размер файла может быть сохранен в архиве? Последний файлик, который мы сохранили, имеет размер 29. При этом у нас еще остается некоторое незанятое место в архиве. Оно равно 8200-8147 = 53. Значит, последний в нашем списке файл, равный 29 можно заменить на любой, размером до 53. Ищем максимально близкий к этому размеру файл. Видим, что его размер равен 50, так как следующий уже – 70. Файл размером 70 не войдет ни при каких обстоятельствах, поэтому заменяем значение в ячейке А569 на 50. Получаем, что свободное место на диске становится равным 3, и его уже не удастся полностью занять.
Второе число для ответа на вопрос задачи равно 50, это максимальный размер файла может быть сохранен в архиве.
Ответ: 568 50
Задача №2 (2638)
В магазине электроники раз в месяц проводится распродажа. Из всех товаров выбирают K товаров с самой большой ценой и делают на них скидку в 20%. По заданной информации о цене каждого из товаров и количестве товаров, на которые будет скидка, определите цену самого дорогого товара, не участвующего в распродаже, а также целую часть от суммы всех скидок.
Входные и выходные данные. В первой строке входного файла 26-k1.txt находятся два числа, записанные через пробел: N – общее количество цен (натуральное число, не превышающее 10 000) и K – количество товаров со скидкой. В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке. Запишите в ответе два числа: сначала цену самого дорогого товара, не участвующего в распродаже, а затем целую часть от суммы всех скидок.
Пример входного файла:
10 3
1800
3600
3700
800
2600
2500
1800
1500
1900
1200
При таких исходных данных ответ должен содержать два числа – 2500 и 1980. Пояснение: скидка будет на товары стоимостью 3700, 3600, 2600. Тогда самый дорогой товар без скидки стоит 2500, а сумма скидок 740+720+520 = 1980.
Решение
Обдумаем механизм распродажи в магазине. Берутся K самых дорогих товаров и на них объявляется скидка 20%. Рассмотрим данные из примера. В магазине 10 товаров, из них три самых дорогих продаются со скидкой. Сортируем товары по убыванию цены, то есть от самого дорогого до самого дешевого. Видим, что это будет товар стоимостью 3700, потом 3600, потом 2600, потом 2500, и т.д., дальше нам не интересно, так как в распродаже участвуют только три товара. Видим, что самый дорогой товар без скидки будет стоить 2500. А на каждый из первых трех товаров применяется скидка 20%, то есть их стоимость нужно умножить на 0,2. Получается 740, 720 и 520, суммируем, получается сумма скидок, равная 1980. Ответ к примеру – 2500 и 1980.
Определили алгоритм решения задачи: сортировать список товаров по убыванию цены, найти в списке стоимость самого дорого, не участвующего в распродаже – это будет первое число в ответе на задачу, для поиска второго числа — умножить стоимости товаров, участвующих в распродаже на величину скидки и сложить получившиеся значения.
Откроем файл в LibreCalc. Общее количество цен равно 1000, количество товаров со скидкой – 100. Переместим эти значения правее, а список цен отсортируем в порядке убывания. В 101 строке будет стоимость первого товара, на который не будет применяться скидка. Озаглавим столбец B «скидка 20%» и будем в нем считать стоимость товаров со скидкой. В ячейке B2 укажем формулу =A2*20% и распространим её на 100 строк вниз, до 101ой строки, так как в первой строке файла находятся заголовки. Выделим строки зеленым цветом для наглядности.
Цена самого дорогого товара, не участвующего в распродаже равна 9000, первое число для ответа на задачу.
Второе число для ответа на задачу посмотрим в строке состояния, выделив значения в столбце B:
Целая часть от суммы всех скидок равна 190680.
Ответ: 9000 190680
Задача №3 (2648)
Магазин предоставляет оптовому покупателю скидку по следующим правилам:
− на каждый второй товар ценой больше 100 рублей предоставляется скидка 10%;
− общая цена покупки со скидкой округляется вверх до целого числа рублей;
− порядок товаров в списке определяет магазин и делает это так, чтобы общая сумма скидки была наименьшей.
Вам необходимо определить общую цену закупки с учётом скидки и цену самого дорогого товара, на который будет предоставлена скидка.
Входные данные. Первая строка входного файла 26-s1.txt содержит число N – общее количество купленных товаров. Каждая из следующих N строк содержит одно целое число – цену товара в рублях. В ответе запишите два целых числа: сначала общую цену покупки с учётом скидки, затем цену самого дорогого товара, на который предоставлена скидка.
Пример входного файла
7
225
160
380
95
192
310
60
В данном случае товары с ценой 60 и 95 не участвуют в определении скидки, остальные товары магазину выгодно расположить в таком порядке цен: 380, 160, 225, 192, 310. Скидка предоставляется на товары ценой 160 и 192. Суммарная цена этих двух товаров со скидкой составит 316,8 руб., после округления – 317 руб. Общая цена покупки составит: 60 + 95 + 317 + 380 + 225 + 310 = 1387 руб. Самый дорогой товар, на который будет получена скидка, стоит 192 руб. В ответе нужно записать числа 1387 и 192.
Решение
Разберемся с условием задачи и наметим план решения.
Магазин предоставляет оптовому покупателю скидку по следующим правилам: на каждый второй товар ценой более 100 рублей действует скидка 10%. Итоговая сумма покупки округляется вверх до целого числа рублей. Порядок товаров в списке определяет магазин и выбирает его так, чтобы общая сумма скидки была минимальной.
Во входных данных в первой строке указано количество товаров, в следующих строках — цены каждого товара в рублях.
Важно учитывать, что скидка применяется только к товарам дороже 100 рублей; скидка даётся ровно на половину таких товаров (каждый второй); магазин минимизирует скидку, значит выбирает для неё самые дешёвые подходящие товары.
Следовательно, все товары дороже 100 рублей нужно отсортировать по возрастанию и применить скидку к каждому второму из самых дешёвых. Остальные товары оплачиваются без скидки.
После этого посчитаем общую стоимость покупки с учётом скидок и выполним округление её вверх; отдельно определим самый дорогой товар, на который была предоставлена скидка.
Именно эти два значения и требуется вывести в ответе.
Откроем файл в LibreCalc. Видим в первой ячейке число 1000 — общее количество купленных товаров. Переместим его правее. Отсортируем список цен товаров по возрастанию и переместим те из них, что не участвуют в акции в столбец D, озаглавим его «Не больше 100», столбец А озаглавим «Больше 100», выделим его и отсортируем по возрастанию – ячейки со значениями «подтянутся» вверх:
Выделим значения в первом столбце, посмотрим в строке состояния количество товаров, участвующих в акции, оно равно 921. Каждый второй товар из них, то есть всего 460 штук – продается со скидкой 10%. Это самые дешевые товары из нашего списка. Посчитаем скидку на эти товары в столбце В. Укажем в ячейке В2 формулу =A2*10%, и распространим её вниз на 460 ячеек:
В ячейке H5 посчитаем общую сумму закупки с учетом скидки, укажем формулу =СУММ(A:A)+СУММ(D:D)-СУММ(B:B). Округляем получившееся число вверх до целого и получаем первое число для ответа на задачу, оно равно 499078.
Цену на самый дорогой товар, на который была предоставлена скидка, посмотрим в ячейке А462:
Цена равна 550, это второе число для ответа на задачу.
Ответ: 499078 550
Задача №4 (5379)
(ЕГЭ-2022) В супермаркете проводится акция «каждым четвёртый товар в чеке за полцены». Покупатель расположил товары на ленте так, чтобы заплатить за покупку одним чеком как можно меньше с учётом проходящей акции. Однако выяснилось, что программа для кассового аппарата не учитывает расположение товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки в рублях была максимально возможной.
Входные данные представлены в файле 26-90.txt следующим образом. В первой строке входного файла записано число N – количество товаром, которые хочет оплатить покупатель (натуральное число, не превышающее 10 000). В каждой из следующих N строк записана цена товара (натуральное число, не превышающее 10 000).
Запишите в ответе два целых числа: сначала сумму, которую предполагал заплатить покупатель, а затем сумму, которую он заплатил за товары.
Пример входного файла:
4
80
30
50
40
При таких исходных данных если «каждый третий товар за полцены», предполагаемая и действительная суммы равны 0,5·80 + 30 + 50 + 40 = 160 и 80 + 0,5·30 + 50 + 40 = 185. Ответ: 160 185.
Решение
Проанализируем пример. Покупатель разложил товары так, чтобы со скидкой 25% был самый дорогой товар, то есть тот, что стоит 80. Он хотел получить скидку в 25% от этого значения, то есть заплатить 30 + 40 + 50 + 0,75*80 = 160. Кассовый аппарат настроен так, что скидка в 25% применяется к самому дешевому товару из 4х, независимо от порядка их выкладки. В примере скидка будет применена к товару ценой 30, и покупатель заплатит 40+50+80+ 0,75*30 = 185. В ответе пишутся два числа – 160 (сколько хотел бы заплатить покупатель) и 185 (сколько он заплатит).
Откроем приложенный к задаче файл в LibreCalc. Видим в первой ячейке число 10000 — общее количество купленных товаров. Переместим его правее. Отсортируем список цен товаров по убыванию, что бы узнать, какую сумму хотел заплатить покупатель – в верхней части списка у нас окажутся самые дорогие товары, покупатель рассчитывал, что на четверть самых дорогих товаров из списка ему будет скидка 50%.
Посчитаем цену, которую хотел заплатить покупатель в ячейке D4, укажем формулу =СУММ(A1:A2500)*0,5+СУММ(A2501:A10000) – сумму четвертой части всех товаров (2500 из 10000 товаров) со скидкой в 50% и оставшейся части товаров без скидки:
В ячейке E5 посчитаем цену, которую заплатит покупатель. Отсортируем столбец А по возрастанию, число в ячейке D5 изменится, скопируем его в ячейку Е5:
Затем вернем сортировку столбца А обратно:
Получили два числа для ответа на задачу.
Ответ: 39434611 48825239
Задача №5 (5325)
(ЕГЭ-2022) В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрешки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные представлены в файле 26-89.txt следующим образом. В первой строке входного файла записано число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В каждой из следующих N строк находится значения длины стороны очередной коробки (натуральное число, не превышающее 10 000).
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Пример входного файла:
5
43
40
32
40
30
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно. В обоих случаях количество коробок равно 3, а максимальная длина стороны самой маленькой коробки равна 32. Ответ: 3 32.
Решение
Проанализируем пример. Размер подарка позволяет поместить его в самую маленькую коробку. Можно собрать коробки двумя способами – 30, 40, 43. Либо 32, 40, 43. В любом случае, получается собрать 3 коробки, при этом максимальный размер самой маленькой оказывается равным 32.
В подобных задачах работает логика жадного алгоритма. Есть такое понятие «Жадный алгоритм» — он забирает то, что сразу можно забрать. В чем смысл заключается? Мы, когда будем собирать коробки, мы всегда будем собирать коробки первые, подходящие по размеру: если коробку можно взять, мы ее будем сразу брать и класть внутрь. Чем меньше разница между коробками, тем больше места остаётся для остальных коробок.
Откроем приложенный к задаче файл в LibreCalc. Видим в первой ячейке число 10000 — общее количество коробок. Переместим его правее. Отсортируем размеры коробок по убыванию. Далее в ячейке В2 укажем формулу =ЕСЛИ(B2-A3>=3;A3;B2): если разница между размером следующей коробки и предыдущей превышает 3, то меняем размер предыдущей коробки на размер следующей, то есть теперь следующая коробка становится «внутренней». Обрабатываем так все значения столбца А:
Далее копируем значение в ячейке С2 укажем размер первой коробки и с помощью формулы =ЕСЛИ(B3<B2;B3;»») оставляем только уникальные значения размеров коробок: Если значение в текущей ячейки не совпадает со значением в предыдущей в столбце, то копируем его, в противном случае оставляем ячейку пустой (“”):
Выделим столбец С и в строке состояния посмотрим количество коробок, которые удастся вложить:
Число 331 – это первое число для ответа на задачу.
Самая маленькая вложенная коробка при этом равна 10, это значение можно посмотреть в конце списка:
Указываем в ответе на задачу числа 331 и 10.
Ответ: 331 10
Задача №6 ()
Строительная организация возводит два высотных здания, находящихся на расстоянии M друг от друга. Из-за коммунальной аварии потребовалось срочно протянуть трубу от одного здания к другому. В распоряжении организации имеется N труб единичной длины. Известен диаметр каждой трубы. Трубы можно скреплять между собой только при условии, что их диаметр отличается не более чем на 11 единиц.
Пропускной способностью называется минимальный диаметр среди всех труб, из которых построена трасса. Определите максимальную пропускную способность полученной трассы. Для найденного значения пропускной способности определите самый большой диаметр трубы, использованный в данной трассе при условии, что компания хочет сэкономить на трубах и возьмет трубы как можно меньшего диаметра.
Запишите в ответе два числа: максимально возможную пропускную способность трубы и максимальный диаметр трубы.
Входные данные
В первой строке входного файла находятся два числа: N – количество имеющихся труб (натуральное число, не превышающее 20 000) и M — расстояние между зданиями (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит натуральные числа, не превышающие 2000: диаметры труб.
Пример входного файла:
7 3
2
6
7
8
8
10
15
Для приведённого примера можно составить трассы 6 + 7 + 8, 6 + 8 + 8, 7 + 8 + 8, 8 + 8 + 10, максимальная пропускная способность возможна при варианте 8 + 8 + 10, ответом является пара чисел: 8 10.
Решение
Рассмотрим приведенный пример: всего 7 труб, из них нужно составить цепочку из 3 труб, потому что у нас первое число, 7 — это сколько труб всего, и 3 — это расстояние между зданиями, то есть сколько труб нам надо соединить. Показано, что можно составить трассы из труб с диаметрами 6, 7, 8 или 6, 8, 8 или 7, 8, 8 или 8, 8, 10. Таким образом максимальная пропускная способность возможна при варианте 8, 8, 10. В ответе указываются два числа – 8, максимальная пропускная способность, и 10 – максимальный диаметр.
Откроем приложенный файл в LibreCalc, разделив на столбцы. Количество имеющихся труб равно 1000, длина цепочки – 120. Переместим эти значения правее, а список диаметров труб отсортируем в порядке убывания. Далее в ячейку В2 скопируем начальный диаметр из ячейки А1, 2000, в ячейке B3 укажем формулу =ЕСЛИ(B2-A3<=11;A3;B2): если разница между диаметром следующей трубы и предыдущей не превышает 11, то мы добавляем эту трубу в цепочку.
Распространяем вычисления до конца списка, смотрим, какой минимальный диаметр трубы мы возьмем, если сварить 120 труб – нумеруем трубы от 1 до 120 в столбце С:
Минимальный диаметр трубы, использованной в цепочке, равен 1745, это первое число для ответа на задачу. Это же число является максимальной пропускной способностью системы.
Теперь попробуем смоделировать экономию, начнем «сваривать трубы» не с максимального диаметра в 2000, а со следующего размера, с 1992. Выполняем те же действия, но теперь первая труба у нас имеет диаметр 1992:
Видим, что максимальная пропускная способность не изменилась, а самый большой диаметр использованной трубы уменьшился с 2000 до 1992.
Если же рассмотреть дальнейшее уменьшение диаметра первой трубы, до 1990, увидим, что уменьшится пропускная способность, трубы с номерами 119 и 120 будут иметь диаметр, меньший 1745, это нам уже не подходит:
Поэтому ответ на задачу – числа 1745 и 1992.
Ответ: 1745 1992
Задача №7 (4859)
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором наибольшее количеством подряд идущих мест, таких что все они уже распределены (заняты). В ответе запишите два целых числа: номер ряда и наибольшее количество подряд занятых мест.
Входные данные представлены в файле 26-69.txt следующим образом. В первой строке входного файла записано одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит пару чисел, разделённых пробелом: ряд и место выкупленного билета (натуральные числа, не превышающие 100000).
Запишите в ответе два числа: сначала номер ряда, затем наибольшее количество подряд занятых мест.
Пример входного файла:
10
5 5
5 6
5 7
16 9
16 3
16 6
20 23
20 28
20 29
20 30
В данном примере максимальное количество подряд идущих занятых мест равно 3 (5 ряд места 5, 6, 7 и 20 ряд места 28, 29,30). Ответ: 20 3.
Решение
Проанализируем пример:
Есть 10 мест занятых. Видим, 5 ряд, заняты 5, 6, 7 место, 3 места подряд. В 16 ряду заняты 3, 6 и 9 место, они идут не подряд. В 20-м ряду есть 23-е место, а также 28-е, 29-е, 30-е. В задаче спрашивается максимальное количество идущих подряд занятых мест. В примере их три штуки, либо в 5м ряду, либо в 20, при этом наибольший номер ряда получается равен 20. В ответе записывается 20 3.
Откроем приложенный файл в LibreCalc. Видим в первой ячейке значение 10000 – количество занятых мест. Переместим это значение правее, а для столбцов А и В сделаем настраиваемую сортировку. Отсортируем столбец А (номера рядов) по убыванию, а потом, если значения в столбце А одинаковые, отсортируем столбец В (места выкупленных билетов) по возрастанию:
Озаглавим Столбец С «Счётчик подряд идущих мест». Указываем в ячейке С1 значение 1, в ячейке С3 формулу =ЕСЛИ(И(A2=A3;B3-B2=1);C2+1;1) – если места расположены в одном ряду (следующее значение в столбце А совпадает с предыдущим), и разность между номерами мест равна единица, то есть места являются соседними, идут подряд), в этом случае счетчик увеличивается на 1. Если условия не выполняются, то счетчик сбрасывается до единицы:
Чтобы найти максимальное количество мест, идущих подряд, посмотрим фильтр:
Видим, что максимальное количество мест, идущих подряд равно 14. Отфильтруем столбец С по этому значению:
Видим, что наибольший номер ряда, в котором идут 14 мест подряд, равен 99. Указываем в ответе на задачу два числа – 99 и 14.
Ответ: 99 14
Задача №8 (5037)
(Досрочный ЕГЭ-2022) В лесополосе осуществляется посадка деревьев: саженцы высаживают рядами на одинаковом расстоянии. Спустя некоторое время с помощью аэросъемки выясняют, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно K неприжившихся саженцев при условии, что справа и слева от них саженцы прижились.
Входные данные представлены в файле 26-79.txt следующим образом. . В первой строке записаны два числа: N – количество занятых мест (натуральное число, не превышающее 10 000) и K – длина цепочки неприжившихся саженцев, которую нужно найти. Каждая из следующих N строк содержит сведения об одном прижившемся саженце – два натуральных числа, не превышающих 100 000: номер ряда и номер саженца в ряду.
В ответе запишите сначала наибольший номер ряда, затем наименьший номер неприжившегося саженца.
Пример входного файла:
6 3
40 30
40 34
50 125
50 129
50 64
50 68
В примере требуется найти 3 подряд идущих неприжившихся саженца. Ответ: 50 65.
Решение
Во входных данных в первой строке указано количество занятых мест, то есть мест, где саженцы прижились. Далее в каждой из следующих строк записаны два натуральных числа, описывающие положение одного прижившегося саженца. Таким образом, нам известны все места, где саженцы прижились, а пустые места нужно определить косвенно.
По условию требуется найти цепочку из заданного количества подряд идущих неприжившихся саженцев. В примере необходимо найти 3 подряд пустых места.
Идея решения такая: если рассмотреть два соседних прижившихся саженца, то количество пустых мест между ними равно разности их номеров минус один. Например, если прижившиеся саженцы находятся на местах 64 и 68, то между ними есть три пустых места: 65, 66 и 67. Разность номеров равна 4, что и указывает на наличие нужной цепочки.
В ответе требуется указать номер ряда, в котором найдена такая цепочка (в примере — 50) и наименьший номер неприжившегося саженца в этой цепочке, то есть первое пустое место (в примере — 65).
Откроем приложенный файл в LibreCalc. Видим в первой ячейке значение 10000 – количество занятых мест, и 11 – длина цепочки неприжившихся саженцев. Переместим это значение правее, а для столбцов А и В сделаем настраиваемую сортировку. Отсортируем столбец А (номера рядов) по возрастанию, а потом, если значения в столбце А одинаковые, отсортируем столбец В (места саженцев) по возрастанию:
В столбце С будем искать цепочки неприжившихся саженцев, в ячейке С3 укажем формулу =ЕСЛИ(A3=A2;B3-B2-1;»») — если места расположены в одном ряду (следующее значение в столбце А совпадает с предыдущим), то заполняем ячейку значением разности между числами в столбце В минус один. Если условия не выполняются, то в ячейку не записывается ничего. Выражение для длины цепочки неприжившихся саженцев получили эмпирически, нарисовав схему к примеру в условии задачи.
Отфильтруем столбец С по значению 11 – нас интересует ряд, в котором есть цепочка из такого количества неприжившихся саженцев:
Видим, что это ряд с номером 2261, это первое число для ответа на задачу.
Уберем фильтр со столбца С, сделаем фильтр в столбце А, номер ряда 2261:
Видим, что занятое место перед цепочкой из 11 незанятых – место 5086.
Значит, первый неприжившийся саженец имеет номер 5087, это второе число для ответа на задачу.
Ответ: 2261 5087
Задача №9 (6790)
(ЕГЭ-2023) Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия.
Входные данные представлены в файле 26-128.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия (в минутах от начала суток).
Пример входного файла:
5
10 150
100 110
131 170
131 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, по заявкам 2, 3 и 5. Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам 2, 4, 5. Ответ: 3 180.
Ссылка на видео-разбор с таймингом: https://vk.com/video-205546952_456241717?t=1h36m50s
Решение
Для решения задачи применяется жадный алгоритм. Цель — максимизировать количество мероприятий на временной шкале. Это эквивалентно стремлению оставлять как можно больше свободного времени после каждого выбранного мероприятия, чтобы в оставшийся промежуток поместилось максимальное число следующих.
Поэтому оптимальная стратегия заключается в следующем:
· сначала выбирается мероприятие с наименьшим временем окончания;
· затем из оставшихся выбирается следующее мероприятие, которое начинается не раньше окончания предыдущего и также имеет минимальное возможное время окончания;
· процесс повторяется до тех пор, пока это возможно.
Такой выбор гарантирует, что каждое мероприятие занимает зал минимальное возможное время, а значит, оставляет максимум пространства для остальных. В результате получается наибольшее возможное количество мероприятий.
Для реализации этого алгоритма необходимо отсортировать все заявки по времени окончания и затем последовательно отбирать подходящие мероприятия.
Откроем приложенный файл в LibreCalc. Видим в первой ячейке значение 991 – количество заявок на мероприятия. Переместим это значение правее, а для столбцов А и В сделаем настраиваемую сортировку. Отсортируем столбец В (время окончания мероприятий) по возрастанию, а потом, если значения в столбце В одинаковые, отсортируем столбец А (время начала мероприятия) по возрастанию. Таким образом мы выбираем те мероприятия, которые оканчиваются раньше.
В ячейку С2 скопируем значение 600 – минимальное время окончания мероприятия. В ячейке С3 укажем формулу: =ЕСЛИ(A3>=C2;B3;C2) и распространим её до конца таблицы. Таким образом, если время начала какого-то мероприятия (Значение в столбце А) больше либо равно, чем значение в предыдущей ячейке столбца С, то мы можем его взять и мы его берем и при этом выставляем его время окончания (значение из соответствующей ячейки столбца В). И это время окончания будет минимальным, потому что мероприятия были отсортированы по возрастанию времени окончания. Если же время начала мероприятия меньше, то оставляем прежнее значение:
Найдем теперь уникальные значения. Скопируем число 600 в ячейку D2, в ячейке D3 укажем формулу: =ЕСЛИ(C3>C2;C3;»»). Если значение в текущей ячейке столбца С не совпадает со значением в предыдущей, то копируем его, в противном случае оставляем ячейку пустой (“”).
Выделяем столбец D, в строке состояния смотрим количество значений в нем, это максимальное количество мероприятий, которое можно провести в конференц-зале, первое число для ответа на задачу:
Первое число для ответа на задачу равно 16.
Ответим на второй вопрос задачи. При текущей сортировке мы можем найти самое раннее время окончания последнего мероприятия, оно равно 1028:
В задаче требуется найти самое позднее возможное время окончания последнего мероприятия. Для этого найдем время окончания предпоследнего мероприятия:
Теперь найдем все мероприятия, у которых время начала больше, чем 991. Отфильтруем стандартным фильтром столбец А, время начала – больше или равно 991:
Видим два таких процесса:
Один из них мы уже находили, он заканчивается как можно раньше. А второй – гораздо позже. Мы можем заменить последнее мероприятие в нашем списке на то, что начинается в 992 и заканчивается в 1345. При этом общее количество мероприятий не изменится, останется равным 16, но при этом время окончания будет максимальным, 1345.
Ответ: 16 1345
Задача №10 (8240)
(ЕГЭ-2025) На соревнованиях по спортивному ориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами, начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер – натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем. Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.
Входные данные представлены в файле 26-174.txt следующим образом. Первая строка входного файла содержит число N (натуральное число, не превышающее 1 000 000) – количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: номер спортсмена и номер посещённой им контрольной точки. Запишите в ответе два натуральных числа: максимальное число спортсменов с идущими подряд номерами, посетивших одну и ту же точку, и номер этой точки.
Пример входного файла:
9
41 3
43 125
50 33
42 125
42 126
42 127
41 125
50 126
42 126
Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответ: 3 125.
Решение
Откроем приложенный к задаче файл данных в Libre Calc.
Удалим из первой строки число участников – 59188.
Из таблицы нужно удалить повторы, потому что не важно, если спортсмен посетил несколько раз одну и ту же точку, для этого в первой строке пронумеруем столбцы А и В: 1 и 2. Включаем фильтры, в столбце В выбираем фильтр Фильтр по условию – Стандартный фильтр – Параметры – Без повторений. Имя поля – «-нет-»:
Скопируем получившиеся значения на новый лист. Выбираем настраиваемую сортировку и сортируем сначала столбец В по возрастанию, а потом столбец А по возрастанию:
Столбец С сделаем счетчиком спортсменов, чьи номера соответствуют условию задачи. В ячейке С1 укажем значение 1, в ячейке С2 запишем формулу =ЕСЛИ(И(B3=B2;A3=A2+1):C2+1;1), то есть, если одну и ту же точку (В3=В2) посетили спортсмены с идущими подряд номерами (A3=A2+1), то увеличиваем количество число спортсменов с идущими подряд номерами, посетивших одну и ту же точку, иначе остается значение 1, то есть счетчик сбрасывается. Распространим эту формулу до конца таблицы. Озаглавим столбцы (А – спортсмен, В – точка, С – подряд) и включим фильтры. В столбце С оставим максимальное количество идущих подряд номеров спортсменов, посетивших одну и ту же точку, оно равно 56, это первое число для ответа на задачу.
Второе число для ответа на задачу – наименьший номер контрольной точки, которую посетило наибольшее число спортсменов. Он равен 30113.
Ответ: 56 30113