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

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

Рассмотрим две соседние в отсортированном списке занятые места $x$ и $y$. Между ними могут находиться две соседние свободные позиции, ограниченные занятыми местами слева и справа, если $y-x\geq 3$.$$y-x\geq 3$$

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

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

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

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

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

Две соседние свободные места, ограниченные занятыми местами слева и справа, имеют вид $a+1$ и $a+2$. Поэтому соседние занятые места должны иметь номера $a$ и $a+3$.$$b-a=3$$

Сортируем все диаметры по убыванию. Для каждого выбранного коржа следующий можно взять только тогда, когда разность диаметров соседних выбранных коржей не меньше 4.$$d_i - d_{i+1} \geq 4$$

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

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

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

Для каждого кандидата вычисляем общий результат как сумму баллов за три испытания и собеседование.$$S = b_1 + b_2 + b_3 + b_4$$

Формируем рейтинговый список по трём ключам: общий результат по убыванию, баллы за собеседование по убыванию, ID по возрастанию.

Для каждой заявки обозначим время начала через $start_i$, а время окончания — через $end_i$. Две заявки $j$ и $i$ совместимы, если мероприятие $j$ заканчивается не позднее начала мероприятия $i$.$$end_j \le start_i$$

Отсортируем все заявки по времени окончания. Для каждой заявки $i$ вычислим $dp_i$ — максимальное количество мероприятий в расписании, последним из которых является мероприятие $i$.

Удобно хранить для каждого ряда множество занятых мест, чтобы проверять принадлежность за постоянное время.$$occupied[row] = \{\text{занятые места в ряду}\}$$

Две соседние свободные места с занятыми местами слева и справа имеют вид $x+1$ и $x+2$, при этом места $x$ и $x+3$ заняты, а $x+1$ и $x+2$ не заняты.$$x \in occupied,\quad x+1 \notin occupied,\quad x+2 \notin occupied,\quad x+3 \in occupied$$

Произведение двух целых чисел делится на 11, если хотя бы один из множителей делится на 11. Поэтому для каждого числа достаточно хранить только признак делимости на 11.

При обработке элемента с индексом $i$ допустимыми являются элементы с индексами не больше $i - 4$. Элемент с индексом $i - 4$ именно в этот момент добавляется в счётчики допустимых предыдущих элементов.

Разность элементов пары должна быть чётной, поэтому оба элемента должны иметь одинаковую чётность. Обрабатываем отдельно чётные и нечётные числа.$$a \bmod 2 = b \bmod 2$$

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

Для пары элементов произведение кратно 23 тогда и только тогда, когда хотя бы один элемент пары кратен 23.

При чтении элемента с индексом $i$ допустимыми предыдущими являются элементы с индексами не больше $i-3$. Поэтому перед обработкой текущего элемента в счётчик добавляется элемент, прочитанный три позиции назад.

Представим число $74$ как произведение взаимно простых множителей:$$74 = 2 \cdot 37$$

При последовательной обработке очередного числа достаточно знать количество ранее обработанных чисел четырёх типов: всех чисел; чётных чисел; чисел, кратных $37$; чисел, кратных $74$.

Для каждого числа достаточно знать два булевых признака: делится ли оно на $2$ и делится ли оно на $3$. Это определяет один из четырёх типов числа.

Произведение двух чисел делится на $6$, если среди двух чисел есть хотя бы один множитель $2$ и хотя бы один множитель $3$. Поэтому для очередного числа можно добавить к ответу количество уже обработанных чисел совместимых с его типом.

Для произведения двух чисел быть кратным $14$, в произведении должны присутствовать множители $2$ и $7$. При обработке очередного числа считаем только пары с уже прочитанными числами, поэтому каждая пара учитывается ровно один раз.$$14 = 2 \cdot 7$$

Если текущее число чётное, оно уже содержит множитель $2$, поэтому ему подходят все предыдущие числа, кратные $7$. Если текущее число кратно $7$, ему подходят все предыдущие числа, кратные $2$.

Разложим число $38$ на простые множители: $38 = 2\cdot19$. Произведение двух чисел делится на $38$, если в нём присутствуют множители $2$ и $19$.

Во время последовательного чтения чисел будем хранить только четыре счётчика: количество уже прочитанных чисел, количество чисел, кратных $2$, количество чисел, кратных $19$ и количество чисел, кратных $38$. Эти счётчики занимают…

Будем рассматривать элементы последовательности слева направо. Для элемента с индексом $i$ допустимы только элементы с индексами не больше $i-3$.$$j \leq i-3$$

При обработке очередного элемента добавляем в группу допустимых элемент, который находится ровно на расстоянии 3. Храним количество всех добавленных элементов и количество элементов, кратных 13.

Произведение двух чисел кратно $10$, если среди множителей можно выделить множитель $2$ и множитель $5$. Поэтому достаточно учитывать признаки делимости текущего числа на $2$ и на $5.

Числа обрабатываются слева направо. Храним только четыре счётчика: количество просмотренных чётных чисел $e$, количество чисел, кратных $5$, $f$, количество чисел, кратных $10$, $b$, и уже найденное количество подходящих пар $ans$.