На вход программы поступает последовательность из $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 қадам — толық шешімде
Дана последовательность из $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 қадам — толық шешімде
163ФИПИ 38240D№ 25Күрделі Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 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 қадам — толық шешімде
164ФИПИ 441677№ 25Күрделі В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 10. Фрагмент программы вычисляет значение переменной $s$ по формуле: на каждом шаге цикла к текущему значению $s$…
- 1
Переменная $s$ изначально равна нулю, поэтому после выполнения цикла:$$s=(A[0]-A[1])+(A[1]-A[2])+\ldots+(A[9]-A[10])$$
- 2
Слагаемые с промежуточными элементами массива сокращаются попарно:$$s=A[0]-A[10]$$
Ещё 1 қадам — толық шешімде
165ФИПИ 454C49№ 25Күрделі В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны $4, 5, 3, 2, 1, 7, 8, 9, 9, 3$ соответственно, то есть $A[0]=4$, $A[1]=5$ и т. д…
- 1
Изначально $c=0$, а массив имеет вид $[4,5,3,2,1,7,8,9,9,3]$.
- 2
При $i=1$: $A[0]=4 < A[1]=5$. Увеличиваем $c$ до 1 и меняем элементы местами.$$c=1$$
Ещё 2 қадам — толық шешімде
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 97$. Найдите среди них…
- 1
Введём префиксные суммы $S_0 = 0$ и $S_i = a_1 + a_2 + \dots + a_i$. Сумма подпоследовательности от позиции $l$ до позиции $r$ равна $S_r - S_{l-1}$.
- 2
Сумма будет кратна $97$, если $S_r \bmod 97 = S_{l-1} \bmod 97$. Поэтому для каждого остатка нужно рассматривать префиксные суммы с одинаковым остатком.
Ещё 3 қадам — толық шешімде
167ФИПИ 514F27№ 25Күрделі В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны 2, 6, 4, 7, 8, 1, 0, 2, 9, 3 соответственно, то есть $A[0] = 2$, $A[1] = 6$ и т. д…
- 1
Изначально $A[9] = 3$, а $c = 0$. При $i=0$ значение $A[0]=2$ не больше 3, поэтому обмена нет.
- 2
При $i=1$: $A[1]=6 > 3$. Выполняется обмен, значение $A[9]$ становится равным 6, а $c=1$.
Ещё 3 қадам — толық шешімде
168ФИПИ 615B1C№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Используем две обработки массива: сначала находим минимальный элемент, делящийся на 3, затем изменяем элементы, делящиеся на 3, и выводим результат.
- 2
Например, на Python фрагмент программы может выглядеть так: j = 10001 for i in range(0, n): if a[i] % 3 == 0 and a[i] < j: j = a[i] for i in range(0, n): if a[i] % 3 == 0: a[i] += j print(a[i])
Ещё 1 қадам — толық шешімде
169ФИПИ 672818№ 25Күрделі В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 9. Значения элементов равны 9, 8, 4, 7, 3, 2, 1, 5, 0, 6 соответственно, то есть $A[0]=9$, $A[1]=8$ и т. д…
- 1
Изначально $A[9]=6$, а $c=0$. Проверяем элементы с индексами от 0 до 8.
- 2
При $i=0$ и $i=1$ элементы 9 и 8 не меньше 6, поэтому обмена нет.
Ещё 4 қадам — толық шешімде
170ФИПИ 6F4A08№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Для поиска минимума достаточно просмотреть все элементы массива и рассматривать только те, которые делятся на 3 без остатка.$$a[i] \bmod 3 = 0$$
- 2
Переменную `j` можно изначально установить равной 10001 — числу, большему любого возможного элемента массива. При нахождении подходящего элемента меньшего значения обновляем минимум.$$j = \min\{a[i] \mid a[i] \bmod 3 = 0\}$$
Ещё 3 қадам — толық шешімде
171ФИПИ 77B382№ 25Күрделі Опишите на русском языке или одном из языков программирования алгоритм подсчёта суммы произведений последовательных пар элементов в целочисленном массиве из 30 элементов. Нужно сосчитать сумму…
- 1
Обозначим элементы массива индексами от 0 до 29 и введём переменную S для накопления суммы.$$S = 0$$
- 2
Перебираем первый индекс каждой пары: 0, 2, 4, ..., 28. Второй индекс пары равен $i+1$.$$i = 0, 2, 4, \ldots, 28$$
Ещё 2 қадам — толық шешімде
172ФИПИ 82874B№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Поскольку гарантируется наличие хотя бы одного элемента, оканчивающегося на 0, можно начать поиск минимума со значения $10000$.$$k = 10000$$
- 2
В первом проходе проверяем последнюю цифру каждого элемента. Если элемент оканчивается на 0 и меньше текущего минимума, сохраняем его в переменной $k$.$$a[i] \bmod 10 = 0 \land a[i] < k$$
Ещё 3 қадам — толық шешімде
173ФИПИ 8453A9№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Сначала перебираем все элементы массива и накапливаем сумму тех, которые больше 150 и имеют чётное значение.$$S = \sum_{i=0}^{29} a_i \text{ при } a_i > 150 \text{ и } a_i \bmod 2 = 0$$
- 2
Вторым проходом снова проверяем это условие и заменяем каждый подходящий элемент найденной суммой.$$a_i := S$$
Ещё 2 қадам — толық шешімде
174ФИПИ 860E60№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от −10 000 до 10 000 включительно. Гарантируется, что хотя бы один элемент массива делится нацело на 5…
- 1
Для поиска максимума среди элементов, кратных 5, введём переменную j с начальным значением −10001. Это значение меньше любого возможного элемента массива.$$j = -10001$$
- 2
Просматриваем все элементы массива. Если элемент делится на 5 и превосходит текущий максимум, обновляем значение j.$$a[i] \% 5 = 0 \land a[i] > j \Rightarrow j = a[i]$$
Ещё 2 қадам — толық шешімде
175ФИПИ 9E4759№ 25Күрделі В программе используется одномерный целочисленный массив $A$ с индексами от 0 до 10. Фрагмент программы вычисляет сумму выражений $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 қадам — толық шешімде
Дана последовательность из $N$ натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна $k = 79$. Найдите среди них…
- 1
Обозначим через $S_i$ сумму первых $i$ элементов последовательности, причём $S_0 = 0$. Сумма элементов подпоследовательности от $l+1$ до $r$ равна $S_r - S_l$.
- 2
Эта сумма кратна $79$, если $S_r \bmod 79 = S_l \bmod 79$.
Ещё 2 қадам — толық шешімде
177ФИПИ A9E896№ 25Күрделі Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа — цифры «1». Каждая из последующих цепочек создается так: в очередную строку дважды записывается…
- 1
Обозначим длину строки с номером $n$ через $L_n$. Каждая строка, кроме первой, содержит две копии предыдущей строки и одну цифру номера строки.$$L_1=1,\quad L_n=2L_{n-1}+1$$
- 2
Получаем длины строк:$$L_1=1,\ L_2=3,\ L_3=7,\ L_4=15,\ L_5=31,\ L_6=63,\ L_7=127$$
Ещё 5 қадам — толық шешімде
178ФИПИ BB29EE№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите алгоритм, который находит сумму элементов массива, больших 100 и при…
- 1
Для каждого элемента проверяем два условия: он должен быть больше 100 и не должен делиться на 4 без остатка.$$a_i > 100 \land a_i \bmod 4 \ne 0$$
- 2
В первом проходе складываем все элементы, удовлетворяющие этим условиям.$$S = \sum_{i=1}^{30} a_i$$
Ещё 2 қадам — толық шешімде
179ФИПИ C23C45№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от −10 000 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
В переменной `j` храним максимальный найденный элемент, кратный 4. Так как элементы массива не меньше −10 000, начальное значение −10 001 гарантированно меньше любого элемента массива.$$j = -10001$$
- 2
В первом проходе рассматриваем только элементы, кратные 4, и сохраняем среди них максимум.$$a[i] \bmod 4 = 0 \ \text{и}\ a[i] > j \Rightarrow j := a[i]$$
Ещё 2 қадам — толық шешімде
180ФИПИ C33970№ 25Күрделі Дан целочисленный массив из 30 элементов. Элементы массива могут принимать натуральные значения от 1 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит…
- 1
Выбираем Python. Так как все элементы находятся в диапазоне от 1 до 10 000, начальное значение минимума можно взять равным 10001.$$k = 10001$$
- 2
Первым проходом рассматриваем только элементы, кратные 7, и сохраняем среди них наименьший.$$a[i] \mathbin{\%} 7 = 0 \Rightarrow k = \min(k, a[i])$$
Ещё 2 қадам — толық шешімде