Жадные алгоритмы

Вспомним, как сравнивают числа. Сначала — количество разрядов (в нашем случае во всех числах по 6), а дальше — по разрядам слева направо. Тогда, каждый раз выбирая самый маленький доступный разряд, мы получим и самое маленькое число.

В разрядах могут стоять как максимум цифры 2, 9, 5, 9 соответственно. Однако, если первая цифра равна 2, то вторая не больше 3, и получается как максимум . Значит, в точности не достижимо, а вот число на 1 меньше мы уже получать умеем: 19:59 даёт сумму 24.

Для начала отметим, что жадность здесь не работает! Казалось бы, мы хотим, чтобы число содержало как можно меньше разрядов. Поэтому надо начать с 777, но тогда остается сумма 4, которую нельзя представить одной цифрой, являющейся простым числом. Поэтому будем решать задачу по-другому.

Сначала докажем, что в числе не может быть 4 или менее знаков. Трёх точно не хватит, так как максимальная сумма цифр . Далее рассмотрим четырёхзначные числа. Так как 25 — нечётное число, то 4 цифры не могут быть нечётными. Поэтому как минимум одна цифра равна 2, и тогда сумма оставшихся равна 23, и тремя цифрами, не превосходящими 7, её не получить.

Итак, в числе как минимум 5 знаков. Заметим, что 22777 подходит. При этом числа с одинаковым количеством разрядов мы сравниваем по цифрам слева направо, и цифра 2 — минимально возможная. Поэтому все числа, начинающиеся не на 22, будут больше нашего примера. Оставшиеся цифры равны по 7, так как сумму 21 можно получить только с помощью трёх семёрок.

Пронумеруем все строчки и все столбцы числами от 1 до 100. Тогда нам нужно попасть из клетки (1, 1) в клетку (100, 100). За каждый ход коня одна координата меняется на 1 (+1 или -1), а вторая на 2 (+2 или -2). Будем жадно прыгать к клетке (100, 100). Сначала в клетку (2, 3), потом в (4, 4). Будем продолжать такие прыжки по 2. Тогда получим последовательность клеточек:

(1, 1) -> (4, 4) -> (7, 7) -> …-> (3k + 1, 3k + 1) -> (3(k + 1) + 1, 3(k + 1) + 1) -> ...

Заметим, что закончим мы именно в клетке (100, 100), так как мы побываем на всех клетках вида (3k + 1, 3k + 1), а число 100 представляется в таком виде (дает остаток 1 при делении на 100).

Нам понадобилось ходов.

Проверим оценкой, что наш жадный алгоритм дал лучший результат. За один ход коня сумма координат клетки меняется не более, чем на 3. Тогда, чтобы из суммы 2 получить сумму 200, нужно как минимум ходов.