Занятие 15

Двое играют в следующую игру. Сначала с помощью компьютера генерируется случайное целое число `N_0`, состоящее из двух или более цифр. Затем игроки ходят по очереди, соблюдая следующие правила. Игрок, делающий `i`-ый ход, должен назвать новое число `N_i`, строго меньшее числа `N_{i-1}`, но большее или равное сумме цифр числа `N_{i-1}`. Если игрок не может сделать ход по правилам, то он проигрывает. Например, пусть `N_0`=98. Первый игрок должен назвать число от 17 до 97. Если он назовет 17, то второй игрок назовет 8 и выиграет. Если он назовет 19, то второй игрок должен будет выбрать число от 10 до 18, и какое бы число второй игрок не назвал, первый игрок сможет назвать 9 и выиграть.

Напишите программу, которая вводит натуральное число `N_0\ (10≤N_0<10^101)` и выводит число `N_1` – ход, который позволит выиграть первому игроку при безошибочной игре противников. Если выигрышный ход не существует, то программа должна вывести 0.

98

19