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

Решение.

Для решения этой задачи нам необходимо обработать последовательность из $N$ чисел и найти среди них максимальное, удовлетворяющее конкретному условию. Разберём алгоритм по шагам.

Шаг 1. Анализ условия окончания числа в системе счисления.
Чтобы узнать последнюю цифру числа в системе счисления с основанием $q$, нужно найти остаток от деления этого числа на $q$. В нашем случае основание системы счисления равно $9$. Следовательно, условие «запись числа в 9-ричной системе счисления оканчивается цифрой 1» на языке программирования запишется как: $x \pmod 9 = 1$.

Шаг 2. Поиск максимума.
Для поиска наибольшего числа заведём переменную-аккумулятор (например, max_val). Изначально присвоим ей значение, которое меньше любого возможного входного числа, или специальный флаг (например, $-1$), чтобы в конце проверить, нашлось ли хотя бы одно подходящее число.

Шаг 3. Алгоритм обработки данных.
1. Считываем количество чисел $N$.
2. В цикле от $1$ до $N$ считываем очередное число $x$.
3. Проверяем, выполняется ли для $x$ условие: $x \pmod 9 = 1$.
4. Если условие выполнено, сравниваем $x$ с текущим максимумом. Если $x$ больше, обновляем значение максимума.
5. После завершения цикла проверяем: если максимум изменился, выводим его. Если нет — выводим «NO».

Пример реализации на языке Python:
n = int(input())
max_val = -1
for _ in range(n):
    x = int(input())
    if x % 9 == 1:
        if x > max_val:
            max_val = x
if max_val == -1:
    print("NO")
else:
    print(max_val)

Разбор примера из условия:
Даны числа: $10, 9, 11, 91, 28$.
1. $10 \pmod 9 = 1$ (подходит), $max\_val = 10$.
2. $9 \pmod 9 = 0$ (не подходит).
3. $11 \pmod 9 = 2$ (не подходит).
4. $91 \pmod 9 = 1$ (подходит), $91 > 10$, значит $max\_val = 91$.
5. $28 \pmod 9 = 1$ (подходит), $28 < 91$, максимум не меняется.
Итог: $91$.

Ответ: 91

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