Информатика ЕГЭ — ФИПИ тапсырмаларының жауаптарымен шешімдері

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

Позиция (4, 20) выигрышна для Пети: первым ходом он утраивает вторую кучу и получает сумму 4 + 60 = 64? Нет, при правильном подсчёте после утроения второй кучи получается позиция (4, 60), сумма 64; поэтому этот ход не является немедленной…

При обратном анализе проигрышными для игрока, которому предстоит ход, являются позиции (4, 21), (7, 20), (5, 20). Поэтому в позициях (4, 21) и (7, 20) выигрышная стратегия принадлежит Ване.

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

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

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

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

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

Для очередного числа $x$ перебираем все остатки $r$, отличные от $x \bmod 120$. Пара допустима, если $x$ делится на $7$ или сохранённое число делится на $7$. Поэтому при $x$, кратном $7$, можно брать максимальное сохранённое число любого…

Прочитать строки файлов и выделить координаты звёзд, а также их спектральные классы и классы светимости.

Разбить точки на кластеры, используя условие о прямоугольниках со сторонами $H=6{,}0$ и $W=5{,}5$.

Обрабатываем последовательность слева направо. Поэтому все сохранённые элементы автоматически имеют индекс меньше индекса текущего элемента, что обеспечивает условие $i < j$.

Если текущий элемент равен $x$, то для делимости суммы на $120$ предыдущий элемент $y$ должен иметь остаток $(120 - x \bmod 120) \bmod 120$.$$y \bmod 120 = (120 - x \bmod 120) \bmod 120$$

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

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

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

Пусть текущее число равно $x$, а его остаток по модулю $160$ равен $r$. Если $x$ делится на $7$, то второй элемент пары может быть любым ранее обработанным числом с остатком, не равным $r$. Если $x$ не делится на $7$, второй элемент…

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

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

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

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

Так как 29 — простое число, произведение двух целых чисел делится на 29 тогда и только тогда, когда хотя бы один из множителей делится на 29.$$29 \mid (a \cdot b) \Longleftrightarrow 29 \mid a \;\text{или}\; 29 \mid b$$

Будем последовательно считывать числа. Для текущего числа на позиции $i$ допустимы только элементы с индексами не больше $i-4$. Поэтому храним количество чисел, кратных 29, среди уже считанных элементов, которые можно образовать с текущим.

Преобразуем выражение:$$(S_i-S_j)+(S_k-S_j)=S_i+S_k-2S_j$$

При фиксированном среднем индексе $j$ выгоднее всего выбрать максимальный элемент среди элементов с индексами меньше $j$ и максимальный элемент среди элементов с индексами больше $j$.

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

Если текущее число делится на $7$, второй элемент пары может быть любым предыдущим числом, но его остаток по модулю $200$ должен отличаться от остатка текущего числа. Для такого поиска достаточно хранить два наибольших предыдущих числа с…

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

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

Преобразуем выражение:$$(S_i-S_j)+(S_k-S_j)=S_i+S_k-2S_j$$

При фиксированном среднем индексе $j$ выгодно выбрать максимальный элемент слева от него и максимальный элемент справа от него.$$F_j=\max_{i<j}S_i+\max_{k>j}S_k-2S_j$$

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

Храним четыре максимальных значения: число, делящееся и на 2, и на 13; число, делящееся на 2, но не на 13; число, делящееся на 13, но не на 2; число, не делящееся ни на 2, ни на 13.

Обозначим через $P_i$ сумму первых $i$ элементов последовательности, причём $P_0 = 0$. Тогда сумма элементов на отрезке $[L;M]$ равна $P_M-P_{L-1}$, а сумма элементов на отрезке $[M+1;R]$ равна $P_R-P_M$.$$D=(P_R-P_M)-(P_M-P_{L-1})=P_R-2P_M+P_{L-1}$$

Для каждого правого конца $R$ необходимо найти минимум величины $2P_M-P_{L-1}$ среди всех допустимых пар $L<M<R-1$. При увеличении $R$ в множество допустимых пар добавляется новая пара с $M=R-2$ и всеми допустимыми $L<M$.$$D_R=P_R-\min(2P_M-P_{L-1})$$

Состояние динамического программирования определяется остатком текущей суммы при делении на $109$. Для каждого остатка сохраняется наибольшая возможная сумма.$$dp[r] = \text{максимальная сумма с остатком } r$$

При обработке очередной тройки перебираем только три варианта выбора. Для каждого прежнего остатка $r$ и числа $x$ из тройки обновляем состояние с новым остатком.$$new[(r+x) \bmod 109] = \max(new[(r+x) \bmod 109],\, dp[r]+x)$$

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

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