Тапсырма 25 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

Для пункта с количеством пробирок $q_i$ вычисляем число контейнеров: оно равно округлению вверх $q_i/44$.$$w_i=\left\lceil\frac{q_i}{44}\right\rceil$$

Если лаборатория находится в пункте с координатой $x$, стоимость перевозки равна сумме взвешенных расстояний до всех пунктов.$$C(x)=\sum_{i=1}^{N}w_i|x_i-x|$$

Сначала заведём переменную s для суммы подходящих элементов и обнулим её.

Первым проходом просмотрим все 30 элементов. Если элемент не больше 197 и нечётен, добавим его к сумме.$$a[i] \leq 197 \land a[i] \bmod 2 = 1$$

В начале $s=0$, $n=5$, а $A[5]=12$. При $i=0,1,2,3,4$ условие $A[i]\leq A[5]$ не выполняется.$$20,19,17,41,23>12$$

При $i=5$ условие выполняется: $A[5]=12\leq A[5]=12$. К переменной $s$ прибавляется 5. Обмен элемента с самим собой ничего не меняет.$$s=0+5=5$$

Перебирать все пары нельзя: такой алгоритм имеет сложность $O(n^2)$. Числа нужно обрабатывать слева направо, чтобы в момент обработки числа $x$ рассматривать только ранее встречавшиеся числа.$$i < j$$

Сумма двух чисел делится на $111$, если сумма их остатков по модулю $111$ равна нулю. Для текущего числа $x$ нужен предыдущий элемент с остатком $r = (111 - x \bmod 111) \bmod 111$.$$(a_i + x) \bmod 111 = 0$$

Проверяем числа, начиная с 1 760 907. Для каждого числа ищем разложение на два простых множителя.

Оставляем только те разложения, в которых каждый множитель является простым числом и содержит в записи ровно одну цифру 1.

Введём префиксные суммы $S_i = a_1 + a_2 + \ldots + a_i$, причём $S_0 = 0$.

Сумма подпоследовательности от $l$ до $r$ равна $S_r - S_{l-1}$. Она кратна $53$, если $S_r$ и $S_{l-1}$ имеют одинаковые остатки при делении на $53$.

В массиве из 30 элементов имеется 29 пар последовательных элементов: $(a_1,a_2)$, $(a_2,a_3)$, ..., $(a_{29},a_{30})$.

Сначала принимаем произведение первой пары за максимальное и запоминаем номер первого элемента этой пары: $maxProduct = a_1 \cdot a_2$, $answer = 1$.

Так как число не превышает $10^8$, вместо символа «*» может стоять от 0 до 3 цифр. Перебираем все числа маски 2*1?71 и проверяем их делимость на 1991.

При пустой последовательности и одной цифре подходящих чисел нет.

Проверим значения $N$, делящиеся на 3. При $N=15$ его двоичная жазба имеет вид $1111_2$.

Так как $15$ делится на 3, к записи приписываются три последние двоичные цифры: $111$. Получаем запись $1111111_2$.

Нужно рассматривать только элементы, остаток от деления которых на 3 не равен нулю.$$A[I] \bmod 3 \ne 0$$

Так как подходящий элемент гарантирован, можно найти первый такой элемент и сохранить его как текущий максимум. Например, просмотреть массив слева направо и при первом подходящем элементе записать его в переменную $J$.

Для составного числа $n$ минимальный нетривиальный делитель является минимальным простым делителем $p$. Максимальный нетривиальный делитель равен $n/p$, поэтому $M = p + n/p$.$$M = p + \frac{n}{p}$$

Проверяем числа, начиная с $800001$, и отбираем те, для которых $M$ оканчивается цифрой 4.

Так как число не превышает $10^8$, символ «*» может задавать только пустую последовательность или одну цифру. Перебираем все варианты цифр и проверяем соответствие маске и делимость на 253.$$N=12ab15*6$$

При пустой последовательности найдено число $1278156$. Делим его на 253.$$1278156\div253=5052$$

Обозначим через $c_i$ количество чётных цифр в $i$-й строке. В первой строке чётных цифр нет: $c_1=0$.

При построении каждой следующей строки предыдущая строка записывается дважды, поэтому её вклад удваивается. Дополнительно учитываем чётные цифры в номере строки.$$c_i=2c_{i-1}+e_i$$

Переменная $s$ изначально равна нулю, поэтому после выполнения цикла:$$s=(A[0]-A[1])+(A[1]-A[2])+\ldots+(A[9]-A[10])$$

Слагаемые с промежуточными элементами массива сокращаются попарно:$$s=A[0]-A[10]$$

Проверим числа, имеющие не более шести цифр в двоичной записи. Для чётного числа с $k$ цифрами результат имеет вид $10b_1b_2\ldots b_k$, поэтому $R=2^{k+1}+N$. Для нечётного числа результат имеет вид $1b_1b_2\ldots b_k01$, поэтому…

Наибольшее нечётное число с шестью двоичными цифрами — $63$. Для него $R=2^8+4\cdot63+1=509$, то есть условие ещё не выполняется.

Изначально $c=0$, а массив имеет вид $[4,5,3,2,1,7,8,9,9,3]$.

При $i=1$: $A[0]=4 < A[1]=5$. Увеличиваем $c$ до 1 и меняем элементы местами.$$c=1$$

Начальный массив: $[2, 4, 3, 6, 3, 7, 8, 2, 9, 1]$. При $i=1$ выполняется $2<4$, происходит обмен, $c=1$.$$A=[4,2,3,6,3,7,8,2,9,1]$$

При $i=2,3,4,5,6$ условия также выполняются. После каждого сравнения происходит обмен, поэтому к счётчику добавляется ещё 5.$$c=6$$

Введём префиксные суммы $S_0 = 0$ и $S_i = a_1 + a_2 + \dots + a_i$. Сумма подпоследовательности от позиции $l$ до позиции $r$ равна $S_r - S_{l-1}$.

Сумма будет кратна $97$, если $S_r \bmod 97 = S_{l-1} \bmod 97$. Поэтому для каждого остатка нужно рассматривать префиксные суммы с одинаковым остатком.

У каждого найденного числа три различных простых делителя. Минимальный делитель равен 2, максимальный — 61, поэтому $M = 2 + 61 = 63$.

Число $M = 63$ оканчивается на 63 и делится на количество различных простых делителей: $63$ делится на $3$.

Для каждого пункта заменяем количество пробирок числом контейнеров, округляя вверх до целого:$$w_i = \left\lceil \dfrac{q_i}{40} \right\rceil$$

Если лаборатория расположена в пункте с координатой $x$, стоимость доставки равна:$$S(x)=\sum_{i=1}^{N} w_i\lvert x_i-x\rvert$$