Задание EGEINF65B0A5: Преобразование записи числа

Дано трёхзначное число N = 100a + 10b + c. Цифра a принадлежит отрезку от 1 до 9, а b и c — от 0 до 9. Автомат вычисляет произведения ab и bc и соединяет их десятичные записи по неубыванию. Требуется наибольший вход, дающий 621.

Разберём все варианты разделения строки 621 на два непустых числа. Можно получить 6 и 21 либо 62 и 1. Вариант 62 и 1 не подходит: порядок убывающий. Значит, произведения равны 6 и 21 в некотором порядке. Нулевых цифр среди множителей нет.

Средняя цифра b входит в оба произведения, поэтому делит и 6, и 21. Их общие положительные делители — 1 и 3. При b = 1 один из крайних множителей должен равняться 21, а это не цифра. Остаётся b = 3. Тогда крайние цифры равны 2 и 7: 3 · 2 = 6, 3 · 7 = 21.

Все допустимые входы: 237 и 732. Других вариантов нет: рассмотрены оба разбиения результата, все общие делители и оба порядка крайних цифр.
Из этих двух чисел выбираем 732.

Проверка: 7 · 3 = 21, 3 · 2 = 6. После сортировки получаем 6, 21; соединение записей даёт 621. Исходное число трёхзначное и все его цифры допустимы. Отдельный перебор всех 900 чисел от 100 до 999 также оставляет только 237 и 732.

Ответ: 732.