Задание №16 — Алгоритмы и программирование

Решение.

Для решения этой задачи нам необходимо проанализировать каждое число из последовательности и проверить, удовлетворяет ли оно двум условиям в восьмеричной системе счисления:
1. Число является четырёхзначным.
2. Число оканчивается на цифру $2$.

Разберёмся, как проверить эти условия, не переводя число в восьмеричную систему целиком:

Шаг 1. Проверка на "четырёхзначность" в восьмеричной системе.
Минимальное четырёхзначное число в восьмеричной системе — это $1000_{8}$. Переведём его в десятичную систему:
$1 \cdot 8^{3} + 0 \cdot 8^{2} + 0 \cdot 8^{1} + 0 \cdot 8^{0} = 512_{10}$.
Максимальное четырёхзначное число в восьмеричной системе — это $7777_{8}$. Следующее за ним число — $10000_{8}$, которое равно $8^{4} = 4096_{10}$.
Следовательно, число $X$ является четырёхзначным в восьмеричной системе, если оно находится в диапазоне: $512 \le X < 4096$.

Шаг 2. Проверка последней цифры.
Последняя цифра числа в любой системе счисления с основанием $q$ — это остаток от деления этого числа на $q$.
Чтобы число в восьмеричной системе оканчивалось на $2$, остаток от его деления на $8$ должен быть равен $2$.
Условие: $X \pmod 8 = 2$.

Шаг 3. Алгоритм решения.
1. Считываем количество чисел $N$.
2. Заводим счётчик (переменную count), изначально равный $0$.
3. В цикле от $1$ до $N$ считываем очередное число $X$.
4. Если $(X \ge 512)$ И $(X < 4096)$ И $(X \pmod 8 = 2)$, то увеличиваем счётчик на $1$.
5. После завершения цикла выводим значение счётчика.

Разбор примера:
1. $482$: $482 < 512$ (не подходит, оно трёхзначное в $8$-ой системе: $742_{8}$).
2. $554$: $512 \le 554 < 4096$, но $554 \pmod 8 = 2$. Подходит ($1052_{8}$).
3. $890$: $512 \le 890 < 4096$, $890 \pmod 8 = 2$. Подходит ($1572_{8}$).
4. $3026$: $512 \le 3026 < 4096$, $3026 \pmod 8 = 2$. Подходит ($5722_{8}$).
5. $4122$: $4122 > 4096$ (не подходит, оно пятизначное в $8$-ой системе).
Итого: $3$ числа.

Пример реализации на языке Python:

n = int(input())
count = 0
for _ in range(n):
    x = int(input())
    if 512 <= x <= 4095 and x % 8 == 2:
        count += 1
print(count)

Ответ: 3

Источник: ФИПИ