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

Решение.

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

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

Шаг 2: Поиск минимума.
Чтобы найти наименьшее число, введём переменную-флаг или инициализируем переменную для минимума значением, которое заведомо больше любого возможного входного числа. По условию числа не превышают 30 000, поэтому в качестве начального значения минимума можно взять $30001$.

Шаг 3: Алгоритм действий.
1. Создаём переменную min_val и присваиваем ей значение $30001$.
2. В цикле считываем число $x$. Если $x = 0$, прерываем цикл.
3. Проверяем условие: если $x \pmod 9 = 1$ и при этом $x < min_val$, то обновляем значение минимума: min_val = x.
4. После окончания цикла проверяем, изменилось ли значение min_val. Если оно осталось равным $30001$, значит, подходящих чисел не было, и нужно вывести «NO». В противном случае выводим найденное значение min_val.

Разбор примера:
Ввод: 10, 9, 11, 91, 28, 0.
- 10: $10 \pmod 9 = 1$. Подходит. min_val = 10.
- 9: $9 \pmod 9 = 0$. Не подходит.
- 11: $11 \pmod 9 = 2$. Не подходит.
- 91: $91 \pmod 9 = 1$. Подходит, но $91 > 10$. Минимум не меняем.
- 28: $28 \pmod 9 = 1$. Подходит, но $28 > 10$. Минимум не меняем.
- 0: Конец ввода.
Результат: 10.

Пример реализации на языке Python:
min_val = 30001
while True:
    x = int(input())
    if x == 0: break
    if x % 9 == 1:
        if x < min_val:
            min_val = x
if min_val == 30001:
    print("NO")
else:
    print(min_val)

Ответ: 10

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