На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар…
- 1
Обрабатываем последовательность слева направо. Поэтому все числа, сохранённые к моменту обработки $a_j$, имеют индексы меньше $j$.
- 2
Для текущего числа $a_j$ допустимая сумма должна делиться на $109$. Если $r = a_j \bmod 109$, то предыдущий элемент должен иметь остаток $(109-r) \bmod 109$.
Ещё 5 шагов — в полном решении
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от −10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования…
- 1
Заведём переменную-счётчик $j$ и установим её начальное значение равным нулю.$$j = 0$$
- 2
Переберём все элементы массива. Если остаток от деления элемента на 3 не равен нулю, этот элемент не делится на 3, поэтому увеличим счётчик.$$a[i] \% 3 \ne 0 \Rightarrow j = j + 1$$
Ещё 1 шаг — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. 1. Строится двоичная запись числа $N$. 2. Далее эта запись обрабатывается по следующему…
- 1
Если $N$ делится на 3, дописываются три последние двоичные цифры числа $N$. Их значение равно $N \bmod 8$, поэтому$$R=8N+(N\bmod 8)$$
- 2
Для чисел, делящихся на 3, условию $R<76$ удовлетворяет, в частности, $N=9$: $R=8\cdot9+1=73$. Следующее такое число, $N=12$, уже даёт $R>76$.
Ещё 4 шага — в полном решении
По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения и передаёт его на сервер. Определите три…
- 1
Пусть $a_i$ — значение показания в момент $i$. Для каждого момента нужно учитывать только показания с индексами не больше $i-K$, поскольку между выбранными моментами должно пройти не менее $K$ минут.$$j \leq i-K$$
- 2
Вычисляем лучшие суммы для последовательностей из одного и двух показаний. Для двух показаний к текущему значению добавляется лучший результат для одного показания среди допустимых предыдущих позиций.$$dp_1[i]=a_i,\qquad dp_2[i]=a_i+\max_{j\leq i-K}dp_1[j]$$
Ещё 2 шага — в полном решении
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от $-10\,000$ до $10\,000$ включительно. Опишите на естественном языке или на одном из языков…
- 1
Последовательно просматриваем все элементы массива.$$i = 1,2,\ldots,20$$
- 2
Если очередной элемент не делится на 7, проверяем, больше ли он текущего максимума. Для первого подходящего элемента удобно отдельно установить начальное значение максимума.
Ещё 2 шага — в полном решении
Пусть $M$ — сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, значение $M$ считается равным нулю. Напишите…
- 1
Перебираем натуральные числа в порядке возрастания, начиная с числа, следующего за $8\,007\,524\,668$.$$n = 8\,007\,524\,669, 8\,007\,524\,670, \ldots$$
- 2
Оставляем только числа, в десятичной записи которых последовательность 991 встречается ровно один раз.$$\operatorname{count}(\operatorname{str}(n),991)=1$$
Ещё 2 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для удобства программа представлена на пяти языках программирования.
- 1
Изначально $s = 0$ и $n = 86$. На каждой итерации цикла значение $s$ увеличивается на 8.$$s = 8k$$
- 2
Минимальное число итераций, при котором $s \geq 71$, равно 9: после 8 итераций $s = 64$, после 9 итераций $s = 72$.$$8 \cdot 9 = 72$$
Ещё 2 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от $0$ до $9$. Значения элементов равны $6, 9, 7, 2, 1, 5, 0, 3, 4, 8$ соответственно. Определите значение переменной $c$…
- 1
Изначально массив имеет вид $[6, 9, 7, 2, 1, 5, 0, 3, 4, 8]$, а $c=0$.
- 2
При $i=0$: $6<9$, поэтому выполняется обмен, $c=1$. При $i=1$: $6<7$, выполняется обмен, $c=2$.
Ещё 4 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$. Сначала строится двоичная запись числа $N$. Если число $N$ чётное, к этой записи справа и слева…
- 1
Проверим небольшие значения $N$, так как требуется найти максимальный результат, не превышающий 56.
- 2
Для нечётного числа $N=5$ двоичная запись имеет вид $101_2$. По правилу получаем $1\,101\,00_2=110100_2$.
Ещё 2 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы.
- 1
В начале $s = 40$, а на каждой итерации цикла значение $s$ уменьшается на $7$.$$40 \to 33 \to 26 \to 19 \to 12 \to 5 \to -2$$
- 2
Пока $s > 0$, значение $n$ умножается на $2$. Условие цикла выполняется $6$ раз.$$n = 1 \cdot 2^6$$
Ещё 1 шаг — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 11. Значения элементов равны 20, 19, 17, 41, 23, 12, 24, 16, 4, 13, 6, 15 соответственно, то есть $A[0] = 20$…
- 1
Так как $n = 0$ и значение $n$ не изменяется, на каждом шаге сравниваются $A[i]$ и $A[0]$. При выполнении условия к $s$ прибавляется индекс $i$, после чего элементы $A[i]$ и $A[0]$ меняются местами.$$s := s + i$$
- 2
Последовательно отслеживая изменения массива, получаем срабатывание условия при индексах $i = 0, 1, 2, 5, 8$.
Ещё 1 шаг — в полном решении
Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна…
- 1
Пара последовательных элементов может начинаться с любого номера от 1 до 29.
- 2
Сначала принимаем первой парой элементы с номерами 1 и 2: сохраняем их сумму и номер 1.
Ещё 4 шага — в полном решении
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Заведём счётчик подходящих элементов и обнулим его.$$j = 0$$
- 2
Первым проходом просмотрим все элементы массива. Элемент учитывается, если он больше 100 и остаток от деления на 4 не равен нулю.$$a[i] > 100 \land a[i] \bmod 4 \ne 0$$
Ещё 2 шага — в полном решении
По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на сервер…
- 1
Нумеруем показания от $0$ до $N-1$. Для текущего показания $a_i$ предыдущие выбранные показания должны иметь индексы не больше $i-K$.
- 2
Поддерживаем три величины: максимальное значение одного допустимого показания, максимальную сумму пары, второй элемент которой уже допустим для текущего положения, и максимальную найденную сумму трёх показаний.
Ещё 3 шага — в полном решении
Напишите программу, которая перебирает целые числа, большие 600 000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 9 и не равный ни…
- 1
Перебираем числа, начиная с 600001. Для каждого числа проверяем делители в порядке возрастания и выбираем первый делитель, оканчивающийся цифрой 9, кроме 9 и самого числа.$$n \bmod d = 0,\quad d \bmod 10 = 9,\quad d \ne 9,\quad d \ne n$$
- 2
Для числа 600001 наименьший подходящий делитель равен 19: $600001 = 19 \cdot 31579$.
Ещё 4 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится двоичная запись числа $N$. Если сумма цифр в двоичной записи чётная, к…
- 1
Проверяем числа по возрастанию. Для $N=21$ двоичная запись имеет нечётное число единиц:$$21_{10}=10101_2$$
- 2
Поэтому справа дописывается $1$, затем первые два разряда заменяются на $11$:$$10101_2\to101011_2\to111011_2=59_{10}$$
Ещё 2 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны $3, 1, 7, 6, 5, 4, 8, 2, 9, 0$ соответственно, то есть $A[0]=3$, $A[1]=1$ и т. д…
- 1
Начинаем с массива $[3,1,7,6,5,4,8,2,9,0]$ и $s=0$. При $j=0$ выполняется условие $3>1$, поэтому $s=1$, после обмена массив становится $[1,3,7,6,5,4,8,2,9,0]$.$$s=1$$
- 2
При $j=1$ условие $3>7$ ложно. При $j=2$ выполняется $7>6$: $s=2$, после обмена массив становится $[1,3,6,7,5,4,8,2,9,0]$.$$s=2$$
Ещё 3 шага — в полном решении
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар…
- 1
Последовательность просматривается слева направо. В момент обработки числа $x = a_j$ в таблице уже находятся только элементы $a_i$ с индексами $i < j$, поэтому порядок элементов пары автоматически соблюдается.$$i < j$$
- 2
Сумма $y + x$ делится на $117$, если остаток числа $y$ равен $(-x) \bmod 117$. Для каждого остатка храним максимальное предыдущее число с таким остатком и само число для вывода.$$(y + x) \bmod 117 = 0$$
Ещё 5 шагов — в полном решении
По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут ($N$ — натуральное число) прибор ежеминутно регистрирует значение напряжения в электрической…
- 1
Нумеруем показания последовательности начиная с единицы. Для трёх выбранных позиций $i<j<l$ должны выполняться условия $j-i\geq K$ и $l-j\geq K$.
- 2
Для каждой позиции поддерживаем максимальное произведение пары чисел, выбранных среди уже доступных позиций с необходимым расстоянием. При обработке очередного числа учитываем только позиции, отстоящие от него минимум на $K$.
Ещё 2 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для удобства программа представлена на пяти языках программирования.
- 1
В начале $s = 50$, $n = 1$. На каждой итерации $s$ заменяется на результат целочисленного деления на 2, а $n$ умножается на 2.$$s: 50 \to 25 \to 12 \to 6 \to 3 \to 1 \to 0$$
- 2
После шестой итерации значение $s$ становится равным 0, поэтому цикл завершается.$$n = 1 \cdot 2^6 = 64$$