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

Решение.

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

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

Шаг 2: Инициализация переменной для поиска минимума.
Для поиска минимального значения нам нужна переменная-аккумулятор (назовём её min_val). Изначально ей нужно присвоить значение, которое заведомо больше любого возможного числа в последовательности. По условию числа не превышают $30\,000$, поэтому мы можем взять $30\,001$ или любое другое число больше этого порога.

Шаг 3: Обработка последовательности.
Мы считываем количество чисел $N$, а затем в цикле проходим по каждому числу:
1. Считываем текущее число $x$.
2. Проверяем условие: $x \pmod 9 = 1$.
3. Если условие выполняется, сравниваем $x$ с текущим минимумом min_val. Если $x < min\_val$, обновляем значение min_val.

Шаг 4: Вывод результата.
После завершения цикла проверяем, изменилось ли значение min_val. Если оно осталось прежним (равным $30\,001$), значит, подходящих чисел не нашлось, и нужно вывести «NO». В противном случае выводим найденное значение min_val.

Пример кода на языке Python:
n = int(input())
min_val = 30001
for _ in range(n):
    x = int(input())
    if x % 9 == 1:
        if x < min_val:
            min_val = x
if min_val == 30001:
    print("NO")
else:
    print(min_val)

Разбор примера:
Входные данные: $10, 9, 11, 91, 28$.
1. $10 \pmod 9 = 1$. Подходит. min_val = $10$.
2. $9 \pmod 9 = 0$. Не подходит.
3. $11 \pmod 9 = 2$. Не подходит.
4. $91 \pmod 9 = 1$. Подходит, но $91 > 10$. min_val остается $10$.
5. $28 \pmod 9 = 1$. Подходит, но $28 > 10$. min_val остается $10$.
Итог: $10$.

Ответ: 10

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