Пусть $M$ — сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите…
- 1
Перебираем числа, начиная с $5\,100\,001$, пока не будут найдены пять подходящих чисел.$$n = 5\,100\,001, 5\,100\,002, \ldots$$
- 2
Для каждого числа раскладываем его на простые множители. Минимальный и максимальный простые множители обозначим $p_{\min}$ и $p_{\max}$.$$M = p_{\min} + p_{\max}$$
Ещё 2 шага — в полном решении
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Для поиска минимума среди чётных элементов задаём начальное значение k, большее любого допустимого элемента массива.$$k = 10001$$
- 2
Просматриваем все элементы массива. Если элемент чётный и меньше текущего значения k, сохраняем его в k.$$a[i] \bmod 2 = 0 \land a[i] < k \Rightarrow k := a[i]$$
Ещё 2 шага — в полном решении
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Выберем первый элемент массива, не делящийся нацело на 5, в качестве начального значения минимума.$$a[i] \mathbin{\%} 5 \ne 0$$
- 2
Просмотрим массив и обновим минимум, если найдём меньший элемент, не делящийся на 5.$$j = \min\{a[i]\mid a[i] \mathbin{\%} 5 \ne 0\}$$
Ещё 2 шага — в полном решении
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 61$. Найдите среди них…
- 1
Введём префиксные суммы $S_0 = 0$ и $S_i = a_1 + a_2 + \ldots + a_i$. Сумма подпоследовательности с номерами от $l+1$ до $r$ равна $S_r - S_l$.
- 2
Эта сумма кратна $61$ тогда и только тогда, когда $S_r$ и $S_l$ имеют одинаковые остатки при делении на $61$.
Ещё 3 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 10. Значения элементов равны 10, 8, 4, 3, 0, 7, 2, 1, 5, 9, 6 соответственно, то есть $A[0] = 10$, $A[1] = 8$ и так…
- 1
Начальное значение переменной равно $s = 0$. Последовательно сравниваем соседние элементы массива.$$A = [10, 8, 4, 3, 0, 7, 2, 1, 5, 9, 6]$$
- 2
При $j = 0, 1, 2, 3$ условие $A[j] < A[j+1]$ не выполняется.
Ещё 2 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 10. Фрагмент программы вычисляет значение переменной $s$ по формуле $s := s + A[i] - A[i+1]$ при изменении $i$ от 0…
- 1
Цикл выполняется для $i = 0, 1, \dots, 9$, поэтому переменная $s$ равна сумме соседних разностей.$$s=(A[0]-A[1])+(A[1]-A[2])+\dots+(A[9]-A[10])$$
- 2
Все промежуточные элементы сокращаются: $-A[1]+A[1}$, $-A[2]+A[2]$ и так далее.$$s=A[0]-A[10]$$
Ещё 1 шаг — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы.
- 1
Переменная $s$ принимает значения $0, 10, 20, 30, 40, 50, 60, 70$, после чего цикл выполняется ещё один раз и получает значение 80.$$s: 0 \to 10 \to 20 \to 30 \to 40 \to 50 \to 60 \to 70 \to 80$$
- 2
Условие цикла $s < 71$ выполняется 8 раз. При каждом выполнении переменная $n$ уменьшается на 2.$$n = 66 - 8 \cdot 2$$
Ещё 1 шаг — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 11. Значения элементов равны 5, 8, 7, 11, 10, 12, 9, 6, 4, 13, 3, 15 соответственно, то есть $A[0]=5$, $A[1]=8$ и так…
- 1
В начале $A[0]=5$ и $s=0$. При $i=1$: $8>5$, поэтому выполняется обмен, а $s$ становится равным 1. Теперь $A[0]=8$.
- 2
При $i=2$: $7>8$ — нет обмена. При $i=3$: $11>8$ — обмен, $s=2$, теперь $A[0]=11$.
Ещё 3 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны 6, 3, 4, 8, 7, 9, 5, 2, 0, 1 соответственно, то есть $A[0] = 6$, $A[1] = 3$ и т. д…
- 1
В начале $c=0$, а $A[0]=6$. При $i=1$: $A[1]=3<6$, поэтому $c=1$, после обмена $A[0]=3$.
- 2
При $i=2,3,4,5,6$ текущие значения $A[i]$ не меньше $A[0]=3$, поэтому обмен не выполняется.
Ещё 3 шага — в полном решении
Рассматривается множество целых чисел, принадлежащих числовому отрезку [16 015; 48 989], которые делятся на 7 или 11 и не делятся на 9, 12, 13.
- 1
Сначала считаем числа, кратные 7 или 11:$$N(7\cup11)=N(7)+N(11)-N(77)=4711+2998-429=7280$$
- 2
Исключаем числа, которые дополнительно делятся на 9, 12 или 13:$$N(9)=809,\quad N(12)=607,\quad N(13)=561$$
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит его двоичную запись, анализирует чётность суммы её цифр, дописывает справа соответствующий разряд и заменяет два левых разряда на…
- 1
Если двоичная запись числа $N$ содержит пять разрядов, результат также содержит пять разрядов. При нечётной сумме цифр первые два разряда результата равны $11$, поэтому $R\geq11000_2=48$, что не подходит.$$R\geq 48$$
- 2
Значит, сумма цифр исходной пятиразрядной записи должна быть чётной, а первые два разряда результата равны $10$. Тогда $R<40$ означает, что оставшиеся разряды результата дают число не более $0011_2$.$$R=10abc0_2<101000_2$$
Ещё 2 шага — в полном решении
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от −10 000 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Для хранения максимального чётного элемента используем переменную j. Начальное значение −10001 меньше любого возможного элемента массива.$$j = -10001$$
- 2
Первым циклом просматриваем массив и обновляем максимум только для чётных элементов.$$a[i] \bmod 2 = 0 \land a[i] > j \Rightarrow j = a[i]$$
Ещё 2 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны 9, 13, 10, 3, 1, 7, 0, 4, 5, 12 соответственно, то есть $A[0] = 9$, $A[1] = 13$ и так…
- 1
Начинаем с массива $[9, 13, 10, 3, 1, 7, 0, 4, 5, 12]$ и $c = 0$. При $i = 1$ выполняется условие $9 < 13$, поэтому $c = 1$.
- 2
При $i = 2$ после предыдущего обмена выполняется условие $9 < 10$, поэтому $c = 2$.
Ещё 4 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от $0$ до $9$. Значения элементов массива равны $20$, $19$, $17$, $41$, $15$, $42$, $24$, $56$, $4$, $13$ соответственно…
- 1
В начале $s=0$, а $A[4]=15$. При $i=0$: $20 \geq 15$, поэтому к $s$ прибавляется $20 \bmod 15=5$. После обмена $A[4]=20$.$$s=5$$
- 2
При $i=1$ и $i=2$ условие не выполняется: $19<20$ и $17<20$.
Ещё 4 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от $0$ до $10$. Фрагмент программы выполняет следующие действия: $s := 0$, $n := 10$; для $i$ от $0$ до $n-1$ вычисляется…
- 1
Цикл выполняется для $i$ от $0$ до $9$, поэтому к переменной $s$ добавляется сумма соседних разностей:$$s=(A[0]-A[1])+(A[1]-A[2])+\dots+(A[9]-A[10])$$
- 2
При раскрытии суммы все промежуточные значения массива сокращаются.$$s=A[0]-A[10]$$
Ещё 1 шаг — в полном решении
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного…
- 1
Для пункта с количеством пробирок $q_i$ число контейнеров равно округлению вверх:$$c_i=\left\lceil\frac{q_i}{46}\right\rceil$$
- 2
Если лаборатория находится в пункте с координатой $x_k$, стоимость определяется суммой расстояний до всех пунктов с весами $c_i$:$$S_k=\sum_{i=1}^{N} c_i\lvert x_i-x_k\rvert$$
Ещё 2 шага — в полном решении
Пусть $M$ — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение $M$ равным нулю. Напишите…
- 1
Для каждого составного числа $n$ находим первый делитель $d$ среди чисел от 2 до $\sqrt n$. Тогда $d$ — минимальный нетривиальный делитель, а $n/d$ — максимальный собственный делитель.$$M=d+\frac{n}{d}$$
- 2
Проверяем числа, начиная с $700001$, и отбираем те, для которых последняя цифра значения $M$ равна 4.
Ещё 1 шаг — в полном решении
Пусть $R$ — сумма всех различных натуральных делителей целого числа. Напишите программу, которая перебирает целые числа, большие $500\,000$, в порядке возрастания и ищет среди них такие, для которых…
- 1
Для каждого натурального числа $n$ находим все его делители. Достаточно проверять делители $d$ от 1 до $\lfloor\sqrt n\rfloor$.
- 2
Если $n$ делится на $d$, добавляем к сумме делителей числа $d$ и $n/d$. Если $d^2=n$, добавляем только $d$.
Ещё 2 шага — в полном решении
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного…
- 1
Для каждого пункта с количеством пробирок $q_i$ заранее вычисляется число необходимых контейнеров: $c_i=\left\lceil\dfrac{q_i}{30}\right\rceil$.$$c_i = \left\lfloor\dfrac{q_i+29}{30}\right\rfloor$$
- 2
Так как пункты уже перечислены по возрастанию координаты, для каждого правого конца окна поддерживаются две границы. В окне находятся все пункты, расстояние от которых до текущего пункта не превышает $M$.
Ещё 2 шага — в полном решении
Среди натуральных чисел, не превышающих $10^9$, найдите все числа, соответствующие маске $12345?7?8$ и делящиеся на $37$ без остатка.
- 1
Запишем число, соответствующее маске, в виде $12345a7b8$, где $a$ и $b$ — цифры.$$N=123450708+1000a+10b$$
- 2
Так как $123450708=37\cdot3336505+23$, а $1000\equiv1\pmod{37}$, условие делимости имеет вид:$$23+a+10b\equiv0\pmod{37}$$
Ещё 2 шага — в полном решении