Максимальная достижимая координата x равна 5. Весь столбец x=6 запрещён, поскольку уже сумма цифр x равна 6, независимо от y.
Как найти границу движения муравья по сумме цифр
Максимальная достижимая координата x равна 5. Весь столбец x=6 запрещён, поскольку уже сумма цифр x равна 6, независимо от y.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Муравей стартует в (0,0) на неотрицательной целочисленной сетке и ходит в четыре соседние клетки. Разрешены клетки, где сумма цифр x и y не превышает 5. Как далеко вправо он может попасть?
Ответ
Максимальная достижимая координата x равна 5. Весь столбец x=6 запрещён, поскольку уже сумма цифр x равна 6, независимо от y.
До (5,0) можно дойти по нижней строке. Чтобы попасть в любой столбец правее 6, путь единичными шагами должен пересечь столбец 6, что невозможно. Наличие разрешённых клеток вроде (10,0) не означает их достижимость. Это пример доказательства границы через сплошной барьер до запуска обхода.