Решения заданий ФИПИ ЕГЭ по информатике: «Массивы и строки» — с ответами

Считаем все длины сторон коробок и сортируем их по возрастанию.$$a_1 \leq a_2 \leq \dots \leq a_N$$

Последовательно строим цепочку. Очередную коробку можно добавить, если её сторона отличается от стороны последней выбранной коробки не менее чем на 3.$$a_i-a_{last}\geq 3$$

Считаем, что коробки вложены от меньшей к большей. Для соседних выбранных коробок должно выполняться условие разности сторон не менее 10.$$a_{i+1} - a_i \geq 10$$

Отсортируем все длины сторон по возрастанию.

Для решения необходимо получить пары сроков хранения из прилагаемого входного файла и объединить все $2N$ значений в один список с указанием продукта и типа срока.

Значения следует обрабатывать по возрастанию. Если первым ещё не обработанным значением является срок хранения продукта, его место определяется слева; если это срок годности после вскрытия, его место определяется справа.

Для каждого продукта создаём две записи: срок хранения с момента изготовления и срок годности после вскрытия. Каждой записи сопоставляем номер продукта и тип срока.

Сортируем все записи по возрастанию значения срока. Так как все исходные числа различны, порядок обработки однозначен.

Сгруппируем занятые места по номерам рядов и для каждого ряда определим максимальный номер занятого места.

В ряду с максимальным занятым номером $q$ подходящая пара может начинаться только после этого места. Поэтому проверяем места $q+1$ и $q+2$: если они существуют, то пара $q+1$, $q+2$ свободна, а перед ними нет занятых мест.

Для максимального количества контейнеров выгодно выбирать самые лёгкие контейнеры: замена любого выбранного контейнера на более лёгкий не увеличивает суммарную массу.

Отсортируем массив масс по возрастанию.$$m_1 \leq m_2 \leq \dots \leq m_N$$

Для каждого студента подсчитываем количество оценок, равных 2, и сумму четырёх оценок.$$twos_i = \#\{j \mid grade_{ij}=2\},\quad sum_i=\sum_{j=1}^{4}grade_{ij}$$

Студенты с нулевым количеством двоек сдали сессию. Их сортируем по убыванию суммы оценок, что эквивалентно сортировке по убыванию среднего балла, а при равенстве — по возрастанию ID.

Сгруппируем занятые места по номерам рядов и отсортируем номера мест внутри каждого ряда.$$r \to [m_1, m_2, \ldots, m_k]$$

Два соседних свободных места, ограниченные занятыми местами слева и справа, находятся между двумя занятыми местами, номера которых отличаются на 3.$$m_{i+1}-m_i=3 \Rightarrow (m_i+1,\ m_i+2)$$

Сортируем длины сторон коробок по возрастанию. В цепочке коробки идут в порядке возрастания, а разность между соседними сторонами должна быть не меньше 9.$$a_{i_{k+1}} \geq a_{i_k}+9$$

Для каждого элемента массива справа налево вычисляем максимальную длину цепочки, начинающейся с него. Если следующего подходящего элемента нет, длина цепочки равна 1; иначе к длине цепочки после следующего элемента прибавляем 1.$$dp_i = 1 + dp_j,\quad j=\min\{k>i\mid a_k\geq a_i+9\}$$

Создаём таблицу или словарь, где каждому идентификатору клиента соответствует суммарный объём переданных им данных.$$T_C = \sum S_i$$

Из полученных сумм выбираем значения не менее 150 000 Кбайт и находим сумму двух наименьших таких значений.

Считаем все заявки из файла и сортируем их по времени начала приёма.

Для каждого окна храним момент, с которого оно свободно. Изначально все окна свободны с начала суток.

Два соседних свободных места, ограниченных занятыми местами слева и справа, имеют вид $x+1$ и $x+2$, если заняты места $x$ и $x+3$.$$x \text{ занят},\quad x+3 \text{ занят}$$

В ряду 40 заняты места 3 и 6, поэтому подходящая пара начинается с места 4.

Сформировать сведения о занятых местах для каждого ряда.

В каждом ряду просмотреть места по возрастанию номера. Для свободного места считать количество идущих подряд свободных мест непосредственно перед ним.

Для каждого клиента накапливаем суммарный объём переданных данных в словаре.

Последовательно обрабатываем запросы. Если текущий объём данных в разделе плюс объём очередного запроса превышает вместимость $K$, создаётся резервная копия текущего объёма. Время такой копии соответствует времени текущего запроса, из-за…$$V + S > K$$

Создаём массив времени доступности ячеек, изначально равный нулю.

Для каждой заявки последовательно просматриваем ячейки от первой к последней и выбираем первую ячейку, для которой время доступности меньше времени сдачи багажа.

Считайте из файла количество занятых мест и занесите пары «ряд — место» в структуру данных, позволяющую быстро проверять занятость кресла.

Для каждого ряда и каждого начала пары $j$ от 1 до $K-1$ проверьте, свободны ли места $j$ и $j+1$ в текущем ряду.

Представим каждую заявку как интервал [начало, конец]. Условие совместимости двух последовательных мероприятий: начало следующего должно быть не меньше окончания предыдущего.$$s_{next} \ge e_{last}$$

Отсортируем все заявки по времени окончания. Жадно выбираем очередную заявку, если её время начала не меньше времени окончания последней выбранной заявки.

Считаем размеры коробок из файла и сортируем их по возрастанию. Одинаковые размеры сохраняем, поскольку коробки являются отдельными предметами.$$a_1 \leq a_2 \leq \dots \leq a_N$$

Для фиксированной самой маленькой коробки последовательно выбираем первую подходящую коробку справа: её сторона должна быть не меньше предыдущей стороны плюс 11.$$a_j - a_i \geq 11$$

Считать количество ячеек K и количество заявок N. Для каждой ячейки сохранить время, с которого она свободна; изначально все ячейки свободны.

Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.$$free_i \le t$$

Представим каждую заявку как интервал [начало, окончание]. Мероприятия совместимы, если начало следующего не меньше окончания предыдущего.

Для максимизации количества мероприятий применяем жадный алгоритм: сортируем интервалы по времени окончания и выбираем очередной интервал, если он начинается не раньше окончания последнего выбранного.$$start_i \ge end_{last}$$