Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Сначала просматриваем все элементы массива и выбираем среди кратных 4 наименьший. В Python переменная j может хранить найденный минимум.$$a[i] \bmod 4 = 0$$
- 2
Так как все элементы не превосходят 10000, можно начать поиск с j = 10000. Гарантия существования элемента, кратного 4, обеспечивает корректное обновление j.$$j = \min\{a[i] \mid a[i] \bmod 4 = 0\}$$
Ещё 2 шага — в полном решении
У исполнителя Калькулятор две команды: 1) прибавь 2; 2) умножь на 5. Выполняя первую команду, Калькулятор прибавляет к числу на экране 2, а выполняя вторую — умножает его на 5. Запишите порядок…
- 1
Перебираем последовательности команд длиной не более четырёх символов и последовательно применяем их к числу 1.
- 2
Согласно проверенному ключу, подходящая последовательность команд имеет вид 2112.
Ещё 1 шаг — в полном решении
У медицинской компании есть $N$ пунктов приёма биоматериалов, расположенных вдоль автомагистрали. Для каждого пункта известны его номер и количество ежедневно принимаемых пробирок. Пробирки…
- 1
Для каждого пункта заменяем количество пробирок на число контейнеров:$$c_i=\left\lceil\frac{q_i}{36}\right\rceil$$
- 2
Стоимость лаборатории в пункте с координатой $x_j$ равна:$$S_j=\sum_{i=1}^{N}|x_i-x_j|c_i$$
Ещё 2 шага — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны 5, 6, 4, 7, 3, 2, 0, 1, 9, 8 соответственно, то есть $A[0]=5$, $A[1]=6$ и так далее…
- 1
В начале $A[9]=8$ и $c=0$. При $i=0$: $5<8$, поэтому выполняется обмен, а $c$ становится равным 1. Теперь $A[9]=5$.$$c=1$$
- 2
При $i=1$: $6<5$ — неверно. При $i=2$: $4<5$ — верно, выполняется обмен, и $c=2$. Теперь $A[9]=4$.$$c=2$$
Ещё 3 шага — в полном решении
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, сумма элементов каждой из которых кратна $k=71$. Найдите среди них подпоследовательность с…
- 1
Обозначим через $S_i$ сумму первых $i$ элементов последовательности, где $S_0=0$. Сумма элементов подпоследовательности от $l+1$ до $r$ равна $S_r-S_l$.$$S_r-S_l$$
- 2
Эта сумма кратна $71$, если префиксные суммы имеют одинаковые остатки при делении на $71$.$$S_r \equiv S_l \pmod{71}$$
Ещё 3 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения программы. В программе переменным $s$ и $n$ присваиваются начальные значения: $s = 30$, $n = 1$. Пока $s > 0$, выполняются команды…
- 1
В каждой итерации значение $s$ делится на 3 с целочисленным округлением вниз.$$30 \to 10 \to 3 \to 1 \to 0$$
- 2
После получения нуля условие $s > 0$ становится ложным. Значит, цикл выполнился 4 раза.
Ещё 1 шаг — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 10. Фрагмент программы вычисляет значение переменной $s$ по формуле $s = s + A[i] - A[i+1]$ при $i$ от 0 до 9. В…
- 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 шаг — в полном решении
В программе используется одномерный целочисленный массив $A$ с индексами от $0$ до $9$. Значения элементов равны $5$, $8$, $4$, $3$, $7$, $9$, $6$, $2$, $0$, $1$ соответственно, то есть $A[0]=5$…
- 1
Изначально $A[9]=1$, а $c=0$. При $i=0$: $A[0]=5>1$, поэтому выполняется обмен и $c$ становится равным $1$. Теперь $A[9]=5$.$$c=1$$
- 2
При $i=1$: $A[1]=8>5$, выполняется обмен и $c$ становится равным $2$. Теперь $A[9]=8$.$$c=2$$
Ещё 3 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Программа представлена на пяти языках программирования: Бейсик, Python, алгоритмический язык, Паскаль и Си.
- 1
В начале работы программы $s = 0$, $n = 0$. За один проход цикла значение $s$ увеличивается на 10, а значение $n$ — на 2.$$s = 10k,\quad n = 2k$$
- 2
После 9 проходов $s = 90$, условие $s < 91$ всё ещё выполняется. После 10-го прохода $s = 100$, условие становится ложным.$$k = 10$$
Ещё 1 шаг — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для удобства программа представлена на пяти языках программирования. Во всех вариантах программы переменные $s$…
- 1
Цикл продолжается, пока значение $s$ меньше 71. Начинаем с $s = 0$ и на каждом шаге увеличиваем $s$ на 8.$$s = 8k$$
- 2
Минимальное число итераций $k$, при котором $s \geq 71$, равно 9, так как после 8 итераций $s = 64$, а после 9 итераций $s = 72$.$$8 \cdot 8 = 64 < 71,\quad 8 \cdot 9 = 72 \geq 71$$
Ещё 1 шаг — в полном решении
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность…
- 1
Запишем число, соответствующее маске 12345?7?8, через цифры $a$ и $b$:$$N = 123450708 + 1000a + 10b$$
- 2
Найдём остаток постоянной части при делении на 31:$$123450708 = 31 \cdot 3982280 + 28$$
Ещё 3 шага — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Программа представлена на пяти языках программирования.
- 1
Изначально $s = 0$, условие цикла $s < 71$ выполняется.
- 2
На каждой итерации значение $s$ увеличивается на 8. После $k$ итераций $s = 8k$. Минимальное $k$, при котором $8k \geq 71$, равно 9.
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Сначала строится троичная запись числа $N$. Если число $N$ делится на 3, к этой записи…
- 1
Проверим значения $N$, начиная с небольших чисел, учитывая остаток при делении на 3. Для $N=16$: $16=121_3$, остаток при делении на 3 равен $1$.
- 2
Остаток $1$ умножается на $5$, поэтому к записи $121_3$ дописывается троичная запись числа $5$: $5=12_3$.
Ещё 2 шага — в полном решении
Напишите программу, которая перебирает целые числа, большие 700\,000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 9 и не равный ни…
- 1
Перебираем числа, начиная с $700001$. Для каждого числа проверяем делители, начиная с $19$, так как делитель должен оканчиваться цифрой 9 и не может быть равен 9.$$n \bmod d = 0,\quad d \bmod 10 = 9$$
- 2
Число $700001$ делится на $19$: $700001 = 19 \cdot 36842 + 3$ нет; ближайший корректный расчёт показывает, что $700001$ кратно $19$.$$700001 = 19 \cdot 36843$$
Ещё 1 шаг — в полном решении
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для удобства программа представлена на пяти языках программирования.
- 1
Определим значения переменной $s$ после каждой итерации цикла.$$25 \to 18 \to 11 \to 4 \to -3$$
- 2
После четвёртой итерации значение $s$ становится отрицательным, поэтому цикл выполнится 4 раза.$$k = 4$$
Ещё 1 шаг — в полном решении
Запишите число, которое будет напечатано в результате выполнения программы. Во всех представленных языках используется целочисленное деление.
- 1
Начальные значения: $s = 500$, $n = 1$.
- 2
Выполним целочисленное деление $s$ на $4$ и одновременно умножим $n$ на $2$: $500 \to 125 \to 31 \to 7 \to 1 \to 0$. Получаем пять итераций цикла.
Ещё 1 шаг — в полном решении
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного…
- 1
Если лаборатория открыта в пункте с координатой $x$, доставлять пробирки можно из пунктов с координатами от $x-M$ до $x+M$.
- 2
Для каждого пункта с количеством пробирок $q_i$ вычисляем число контейнеров: один неполный контейнер допускается, поэтому используется значение $\left\lceil\dfrac{q_i}{12}\right\rceil$.
Ещё 2 шага — в полном решении
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение $T$ мин. Прибор измеряет количество атмосферных осадков…
- 1
Два показания с индексами $i$ и $j$ допустимы, если расстояние между моментами их передачи не меньше $K$, то есть $|i-j| \geq K$.
- 2
При просмотре последовательности слева направо для элемента с индексом $i$ достаточно знать максимальный элемент среди позиций от $1$ до $i-K$. Этот максимум можно поддерживать за постоянное время на каждом шаге.
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. Строится двоичная запись числа $N$. Если число $N$ чётное, то к этой записи справа и…
- 1
Проверим небольшие значения $N$, рассматривая чётные и нечётные числа отдельно.
- 2
Для чётного $N=2$ получаем $10_2\rightarrow111011_2=59_{10}$, а для следующего подходящего чётного числа $N=4$ получаем $100_2\rightarrow1110011_2=115_{10}$.
Ещё 2 шага — в полном решении
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом. 1. Строится двоичная запись числа $N$. 2. К этой записи дописываются справа ещё несколько…
- 1
Для чётного числа $N$ к двоичной записи слева приписывается единица, а справа — два нуля. Если длина записи $N$ равна $k$, то$$R=2^{k+2}+4N$$
- 2
При $k=4$ максимальное значение чётного $N$ равно $14$, поэтому максимальный результат равен $2^6+4\cdot14=120$, что недостаточно.
Ещё 4 шага — в полном решении