Задание 26 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Для каждой записи накапливаем сумму цен и количество товаров. Средняя цена вычисляется как сумма всех цен, делённая на $N$.$$\overline{p}=\frac{\sum_{i=1}^{N}p_i}{N}$$

Для каждого артикула подсчитываем число проданных товаров $sold$, число оставшихся товаров $left$ и сохраняем цену артикула.

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

Для двух соседних занятых мест с номерами $a$ и $b$ количество свободных мест между ними равно $b-a-1$. Если первое занятое место в ряду имеет номер $b$, перед ним свободно $b-1$ кресел.$$free=b-a-1$$

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

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

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

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

Из исходной позиции $(3,2)$ первый игрок может получить только четыре различные позиции: $(9,2)$, $(6,2)$, $(3,6)$ или $(3,5)$.

Если первый игрок получил позицию $(9,2)$, второй игрок умножает число камней в первой куче на 3 и получает $27$ камней. Если получена позиция $(3,6)$, второй игрок умножает вторую кучку на 3 и получает $18$ камней, а затем анализ…

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

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

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

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

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

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

Игрок выигрывает одним ходом, если после прибавления одного камня или удвоения количество камней становится не менее 65. При $S \geq 33$ достаточно удвоения. При $S=64$ можно также прибавить один камень.$$2S \geq 65 \Rightarrow S \geq 33; \qquad S+1 \geq 65 \Rightarrow S=64$$

Для задания 1б подходит $S=32$: Петя не может выиграть сразу, но после его хода получаются позиции $33$ или $64$, из которых Ваня выигрывает одним ходом.

Для каждой позиции рассматриваются четыре возможных хода: (a+1,b), (3a,b), (a,b+1), (a,3b). Если после хода сумма не менее 74, ход является немедленно выигрышным.

В позициях (4,23) и (7,22) выигрышная стратегия есть у Вани. После любого хода Пети Ваня получает возможность закончить игру или перевести её в позицию, из которой Петя вынужден открыть Ване немедленную победу.$$W(4,23)=W(7,22)=\text{Ваня}$$

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

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

Задание 1. Из позиции $(14,S)$ можно получить либо $(14+S,S)$ с суммой $14+2S$, либо $(14,14+S)$ с суммой $28+S$.$$14+2S\ge 65 \quad\text{или}\quad 28+S\ge 65$$

Первое неравенство даёт $S\ge 25{,}5$, поэтому при целом $S$ получаем $S\ge 26$. Второе даёт $S\ge 37$. Минимальное подходящее значение — $S=26$; Петя получает позицию $(40,26)$ с суммой 66.$$14+2\cdot 26=66$$

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

Отсортируем массив масс по возрастанию.$$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.

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

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

Сгруппируем занятые места по номерам рядов и отсортируем номера мест внутри каждого ряда.$$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 Кбайт и находим сумму двух наименьших таких значений.

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

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

В первом наборе слова начинаются с разных букв: А и Д. Если Петя начинает с А, все последующие буквы однозначно определены, и слово АБВГДАБВГДХ получается на 11-м ходу. Нечётный номер хода означает победу Пети.$$11 \equiv 1 \pmod 2$$

Если Петя начинает с Д, слово ДГВБАДГВБА получается на 10-м ходу, поэтому победил бы Ваня. Следовательно, выигрышная стратегия Пети — первым написать А, затем каждый раз приписывать единственную возможную букву.$$10 \equiv 0 \pmod 2$$