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

#56312Задание №16ФИПИ

Программирование

Напишите программу, которая в последовательности натуральных десятичных чисел определяет наименьший элемент, запись которого
в системе счисления с основанием 9 оканчивается цифрой 1. Если среди входных данных таких элементов нет, программа должна вывести «NO».

Программа получает на вход в первой строке натуральное число – количество чисел N (3 ≤ N ≤ 10000), затем N натуральных чисел,
не превышающих 30 000, каждое в отдельной строке.

Программа должна вывести одно десятичное число – наименьший элемент последовательности, запись которого в 9-ричной системе счисления оканчивается цифрой 1, или «NO», если среди входных данных таких элементов нет.

Пример работы программы

Входные данные

Выходные данные

Ваше решениедо 2 баллов

Проверка решения с помощью ИИ доступна авторизованным пользователям

Решение.

Для решения этой задачи нам необходимо обработать последовательность из $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

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