printРабочее место участника

printЗадачи

150. Игра с числами

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

Двое играют в следующую игру. Сначала с помощью компьютера генерируется случайное целое число `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
loading