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

Решение.

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

Шаг 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$.
Чтобы число в восьмеричной системе оканчивалось на $1$, остаток от его деления на $8$ должен быть равен $1$.
Условие: $X \pmod 8 = 1$.

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

Пример реализации на языке Python:
n = int(input())
count = 0
for _ in range(n):
    x = int(input())
    if 512 <= x <= 4095 and x % 8 == 1:
        count += 1
print(count)

Разбор примера из условия:
Даны числа: $481, 553, 889, 3025, 4121$.
1. $481$: $481 < 512$ (не четырёхзначное в $8$-й с.с.).
2. $553$: $512 \le 553 < 4096$. Проверяем остаток: $553 = 69 \cdot 8 + 1$. Подходит.
3. $889$: $512 \le 889 < 4096$. Проверяем остаток: $889 = 111 \cdot 8 + 1$. Подходит.
4. $3025$: $512 \le 3025 < 4096$. Проверяем остаток: $3025 = 378 \cdot 8 + 1$. Подходит.
5. $4121$: $4121 > 4095$ (пятизначное в $8$-й с.с.).
Итого: $3$ числа.

Ответ: 3

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