Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
150. Игра с числами
Индукция и другие математические методыПредрешение
Олимпиадные задачи на русском языке
| 23/11/2003 | Районно-городское личное первенство (2) |
| 03/03/2007 | Практическое занятие 15 (D) |
| 28/03/2009 | Занятие 16 (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Двое играют в следующую игру. Сначала с помощью компьютера генерируется случайное целое число `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
