Рассматривается множество целых чисел, принадлежащих числовому отрезку [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 қадам — толық шешімде
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного…
- 1
Для пункта с количеством пробирок $q_i$ вычисляем число контейнеров: оно равно округлению вверх $q_i/44$.$$w_i=\left\lceil\frac{q_i}{44}\right\rceil$$
- 2
Если лаборатория находится в пункте с координатой $x$, стоимость перевозки равна сумме взвешенных расстояний до всех пунктов.$$C(x)=\sum_{i=1}^{N}w_i|x_i-x|$$
Ещё 2 қадам — толық шешімде
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Сначала заведём переменную s для суммы подходящих элементов и обнулим её.
- 2
Первым проходом просмотрим все 30 элементов. Если элемент не больше 197 и нечётен, добавим его к сумме.$$a[i] \leq 197 \land a[i] \bmod 2 = 1$$
Ещё 4 қадам — толық шешімде
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 11. Значения элементов равны 20, 19, 17, 41, 23, 12, 24, 16, 4, 13, 6, 15 соответственно, то есть $A[0]=20$…
- 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$$
- 2
При $i=5$ условие выполняется: $A[5]=12\leq A[5]=12$. К переменной $s$ прибавляется 5. Обмен элемента с самим собой ничего не меняет.$$s=0+5=5$$
Ещё 2 қадам — толық шешімде
На вход программы поступает последовательность из $n$ целых положительных чисел. Рассматриваются все пары элементов последовательности $a_i$ и $a_j$, такие что $i < j$ и $a_i > a_j$. Среди пар…
- 1
Перебирать все пары нельзя: такой алгоритм имеет сложность $O(n^2)$. Числа нужно обрабатывать слева направо, чтобы в момент обработки числа $x$ рассматривать только ранее встречавшиеся числа.$$i < j$$
- 2
Сумма двух чисел делится на $111$, если сумма их остатков по модулю $111$ равна нулю. Для текущего числа $x$ нужен предыдущий элемент с остатком $r = (111 - x \bmod 111) \bmod 111$.$$(a_i + x) \bmod 111 = 0$$
Ещё 5 қадам — толық шешімде
Напишите программу, которая перебирает целые числа, большие 1 760 906, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно…
- 1
Проверяем числа, начиная с 1 760 907. Для каждого числа ищем разложение на два простых множителя.
- 2
Оставляем только те разложения, в которых каждый множитель является простым числом и содержит в записи ровно одну цифру 1.
Ещё 2 қадам — толық шешімде
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 53$. Найдите среди них…
- 1
Введём префиксные суммы $S_i = a_1 + a_2 + \ldots + a_i$, причём $S_0 = 0$.
- 2
Сумма подпоследовательности от $l$ до $r$ равна $S_r - S_{l-1}$. Она кратна $53$, если $S_r$ и $S_{l-1}$ имеют одинаковые остатки при делении на $53$.
Ещё 3 қадам — толық шешімде
Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, произведение которых…
- 1
В массиве из 30 элементов имеется 29 пар последовательных элементов: $(a_1,a_2)$, $(a_2,a_3)$, ..., $(a_{29},a_{30})$.
- 2
Сначала принимаем произведение первой пары за максимальное и запоминаем номер первого элемента этой пары: $maxProduct = a_1 \cdot a_2$, $answer = 1$.
Ещё 3 қадам — толық шешімде
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Так как число не превышает $10^8$, вместо символа «*» может стоять от 0 до 3 цифр. Перебираем все числа маски 2*1?71 и проверяем их делимость на 1991.
- 2
При пустой последовательности и одной цифре подходящих чисел нет.
Ещё 3 қадам — толық шешімде
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$. Сначала строится двоичная запись числа $N$. Если число $N$ делится на 3, к этой записи дописываются три…
- 1
Проверим значения $N$, делящиеся на 3. При $N=15$ его двоичная жазба имеет вид $1111_2$.
- 2
Так как $15$ делится на 3, к записи приписываются три последние двоичные цифры: $111$. Получаем запись $1111111_2$.
Ещё 2 қадам — толық шешімде