Как выполнить Задание "Сон Пифагора" ВСОШ информатика 25.10.24?

Для решения задачи "Сон Пифагора" необходимо определить количество вычитаний, которые Пифагор должен совершить, начиная с заданного натурального числа n, пока не дойдет до нуля. Мы будем вычитать из числа n его последнюю не нулевую цифру, пока не получим 0.

### Шаги решения задачи:

1. Понимание процесса:
   Когда Пифагору снится число n, он начинает его уменьшать. На каждом шаге он вычитает последнюю цифру, которая не равна нулю. Например, для числа 27:
   - 27 - 7 = 20 (последняя цифра 7)
   - 20 - 2 = 18 (последняя цифра 2)
   - 18 - 8 = 10 (последняя цифра 8)
   - 10 - 1 = 9 (последняя цифра 1)
   - 9 - 9 = 0 (последняя цифра 9)
   
   Как видно, здесь мы сделали 5 вычитаний.

2. Основная идея алгоритма:
   На каждом шаге мы будем извлекать последнюю не нулевую цифру и вычитать её из текущего значения n. Для этого используем:
   - Целочисленное деление для получения последней цифры.
   - Вычитание и подсчет шагов.

3. Код на Python:
   Для решения задачи мы можем воспользоваться следующим алгоритмом на языке программирования Python:

def count_subtractions(n):
    count = 0
    while n > 0:
        last_digit = n % 10  # Получаем последнюю цифру
        if last_digit == 0:   # Если она равна 0, ищем следующую
            n //= 10
            continue
        n -= last_digit       # Вычитаем последнюю цифру
        count += 1           # Увеличиваем счетчик
    return count

n = int(input())  # Ввод пользователя
result = count_subtractions(n)  # Вызываем функцию
print(result)  # Вывод результата


### Пояснение к коду:
- Функция `count_subtractions` принимает натуральное число n.
- Внутри функции мы используем цикл `while`, который продолжается, пока n больше 0.
- `n % 10` позволяет получить последнюю цифру, а `n //= 10` убирает её из числа, если она равна 0, мы продолжаем итерацию, не увеличивая счетчик.
- При каждом вычитании мы увеличиваем счетчик `count` и печатаем количество необходимых операций, как только n станет равным 0.

4. Тестирование:
   Вы можете протестировать программу с другими числами, например, 100, 45 или 999, чтобы увидеть, как меняется количество вычитаний.

5. Сложность задачи:
   Алгоритм работает за O(d), где d — это количество цифр в числе n. Для предела в 10^18 максимальное количество итераций будет около 19, что позволит программе выполниться быстро.

Таким образом, мы можем узнать, сколько вычитаний придется сделать Пифагору, используя этот простой алгоритм.