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

Проверяем значения $N$ от меньших к большим, пока результат не достигнет 76.

Для $N=9$ число не изменяется по правилу делимости: к записи $1001_2$ дописываются три последние цифры $001$. Получаем $1001001_2=73<76$.

Цикл выполняется для $i$ от $0$ до $9$, поэтому переменная $s$ получает сумму разностей соседних элементов массива.$$s=(A[0]-A[1])+(A[1]-A[2])+\dots+(A[9]-A[10])$$

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

Подбираем последовательность команд, начиная с числа 1.$$1 \xrightarrow{1} 4 \xrightarrow{2} 8$$

Продолжаем выполнение команд.$$8 \xrightarrow{1} 11 \xrightarrow{2} 22 \xrightarrow{2} 44 \xrightarrow{1} 47$$

Пустая последовательность вместо «*» даёт число 123678, но оно не делится на 13.

При одной цифре вместо «*» получаем числа $1230a678 = 1230678 + 1000a$, где $a$ принимает значения от 0 до 9. Так как $1000 \equiv -1 \pmod{13}$, условие делимости выполняется при $a = 7$. Получаем число 1237678.

Если $N$ не делится на 3 и имеет остаток 1, к двоичной записи дописывается число $3_{10}=11_2$. Поэтому результат равен $R=4N+3$.

Для получения значения, большего 151, в этом случае необходимо $4N+3>151$, то есть $N>37$. Ближайшее число, сравнимое с 1 по модулю 3, — $N=40$.

Проследим положение Робота по программе 3233241. После команд 3 и 2 он находится на клетке, смещённой на одну вправо и одну вниз от исходной.

Команды 3, 3, 2, 4, 1 перемещают Робота по уже пройденному маршруту и приводят его в клетку, достигнутую после первой команды 3.

В начале $c = 0$, а $A[0] = 3$. При $i = 1, 2, 3, 4, 5$ элементы равны 5, 4, 10, 8, 7 и не меньше 3, поэтому замены не происходит.

При $i = 6$: $A[6] = 1 < A[0] = 3$. Увеличиваем счётчик до 1 и меняем элементы местами. Теперь $A[0] = 1$.$$c = 1$$

Изначально $n=1$. На каждой итерации цикла значение $n$ умножается на $2$, поэтому после $k$ итераций $n=2^k$.$$2^k=64$$

Так как $64=2^6$, цикл должен выполниться ровно 6 раз.

Если $N$ делится на 3, приписываются три последние двоичные цифры. Тогда $R = 8N + (N \bmod 8)$. При условии $R \leq 162$ имеем $N \leq 20$.

Если $N \bmod 3 = 1$, к двоичной записи приписывается число $3 = 11_2$. Поэтому $R = 4N + 3$. Из условия $4N + 3 \leq 162$ следует $N \leq 39$. Наибольшее число, не делящееся на 3 и дающее максимальный результат, — $N = 37$.

Для каждого элемента проверяем два условия: он должен быть больше 100 и не должен делиться на 4 без остатка.$$a_i > 100 \land a_i \bmod 4 \ne 0$$

В первом проходе складываем все элементы, удовлетворяющие этим условиям.$$S = \sum_{i=1}^{30} a_i$$

Проследим за изменением переменной $s$ после целочисленного деления на $2$.$$20 \to 10 \to 5 \to 2 \to 1 \to 0$$

После получения значения $s = 0$ условие цикла становится ложным. До этого момента тело цикла выполнилось 5 раз.$$k = 5$$

Последовательность вместо «*» может иметь от 0 до 3 цифр: при 4 цифрах число превысит $10^8$.

При одной цифре получаем условие $123407 + 10x \equiv 0 \pmod{131}$. Оно выполняется при $x=6$5, поэтому найдено число $124057$.

Пронумеруем пункты от $0$ до $N-1$, а количество мусора в пункте $i$ обозначим через $a_i$. Расстояние между пунктами $i$ и $j$ равно $3\cdot\min(|i-j|,N-|i-j|)$.

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

Для каждого числа перебираем делители от 2 до квадратного корня из числа. Первый найденный делитель является минимальным нетривиальным делителем и простым числом.$$d = p$$

Максимальный собственный делитель числа равен частному от деления числа на его минимальный делитель.$$q = \dfrac{n}{p}$$

В переменной `j` храним максимальный найденный элемент, кратный 4. Так как элементы массива не меньше −10 000, начальное значение −10 001 гарантированно меньше любого элемента массива.$$j = -10001$$

В первом проходе рассматриваем только элементы, кратные 4, и сохраняем среди них максимум.$$a[i] \bmod 4 = 0 \ \text{и}\ a[i] > j \Rightarrow j := a[i]$$

Перебор всех троек позиций имеет слишком большую сложность, поэтому состояния нужно обновлять при одном проходе по файлу.$$O(N^3)$$

Пусть $a_i$ — показание в момент $i$. Для каждой позиции поддерживаем минимальную сумму одного, двух и трёх выбранных показаний, причём последние выбранные позиции удовлетворяют ограничению по расстоянию.$$d_1(i)=a_i$$

Выбираем Python. Так как все элементы находятся в диапазоне от 1 до 10 000, начальное значение минимума можно взять равным 10001.$$k = 10001$$

Первым проходом рассматриваем только элементы, кратные 7, и сохраняем среди них наименьший.$$a[i] \mathbin{\%} 7 = 0 \Rightarrow k = \min(k, a[i])$$

Последовательно перебираем целые числа, начиная с числа, следующего за $8\ 007\ 494\ 154$.

Для каждого числа раскладываем его на простые множители. Минимальный и максимальный простые множители складываем: $M=p_{\min}+p_{\max}$.

Проверим числа, меньшие 16. Числа от 1 до 7 имеют не более трёх двоичных разрядов, поэтому после преобразования дают число меньше 190. Для чисел от 8 до 15 рассмотрим наибольшие возможные результаты.

Для чётного числа $N$ к двоичной записи приписываются слева единица и справа два нуля. Для $N=14$ имеем $14_{10}=1110_2$, поэтому $R=1111000_2=120_{10}$.$$1110_2\to1111000_2=120_{10}$$

Определим количество выполнений цикла. Начальное значение $s = 48$, на каждом шаге из него вычитается $7$.$$48 - 7k \leq 0$$

Минимальное целое значение $k$, удовлетворяющее неравенству, равно $7$. Значит, цикл выполняется семь раз.$$k = 7$$