Comments 10
Самая простая стратегия - идти вертикально вниз в каждом ряду. Она гарантированно сработает не более чем за 2023 хода. Так как есть столбец, свободный от монстров.
Более того, в любой оптимальной стратегии потребуется не более 2023 ходов, так как предыдущие ходы выяснят положение всех монстров.
Осталось либо доказать, что нельзя за меньшее число ходов гарантированно прийти к финишу, либо предложить лучшую стратегию.
Сильно подозреваю, что можно меньше. Например, выясним номера строк для монстров в первом, центральном и последнем столбцах, пусть это значения А, В, С. Если они во всех трех оказались, то либо |A - B| != 1011, либо |B - C| != 1011. Там, где это неравенство имеет место, у нас 1012 подряд идущих столбцов, не перегороженных сплошным диагональным "забором", и можно выполнить задачу, используя только эти столбцы, итого 1015 (или 1016) попыток. Но можно продолжить этот бинарный поиск и далее, радикально уменьшив результат до чего-то, похожего на ln(n).
А вот как это наиболее хитро обыграть, да ещё и доказать оптимальность результата - совсем другая история...
Перечитал условия 2 раза, нужно узнать минимальное количество попыток, а не ходов.
Первая попытка: выбираем 2 столбец (x=2) и двигаемся строго вниз, в итоге либо доходим до конца (n = 1), либо утыкаемся в монстра допустим на ряду под номером y.
Вторая попытка: повторяем предыдущий путь, но в ряду y-1 сдвигаемся вправо (x+1, y-1) и дальше вниз (x+1, y) и вниз (x+1, y+1). В итоге либо утыкаемся в монстра (идем на 3 попытку) либо находим пустую клетку, тогда возвращаемся в исходную колонку (x, y+1) и спокойно спускаемся вниз, так как в этой колонке монстра уже нет (n=2).
Третья попытка: повторяем предыдущий путь как и в прошлой попытке, но теперь сворачиваем влево (x-1, y-1), обходим монстра слева (x-1, y) и вниз (x-1, y+1) и возвращаемся в исходную колонку (x, y+1). Слева монстра быть не может, так как монстра мы нашли во 2 попытке, и дальше опять можно спускаться вниз (n=3).
Минимальное количество: n=3.
Третья попытка: повторяем предыдущий путь как и в прошлой попытке, но теперь сворачиваем влево (x-1, y-1)
А с чего вы взяли, что в клетке (x-1, y-1) не монстр?
По факту, надо найти либо столбик без монстра, либо два соседних столбика, у которых клетки с монстрами не граничат по углу (тогда делаем маневр как в вашем втором шаге). Проблема именно в непрерывных диагональных линиях с монстрами, сквозь которые не проскочить. Например, если монстры сидят в клетках (1, y-1), (2, y), (3, y+1), то нельзя ограничиться только лишь колонками 1, 2 и 3.
Да, тоже проснувшись про это подумал. Слишком простое решение за 5 минут чтобы быть правильным :)
Там в окрестности одной точки 7 вариантов размещения монстров, 5 их них просто обходятся, 2 образуют диагональ.
Можно спуститься по средней колонке до первой точки (1012, y)
Проверить точку справа (1013, y-1), если она занята, то у нас предположительно диагональ идет вверх [/].
Будем двигаться от точки (1012, y) вправо и на клетку выше предполагаемой восходящей диагонали [//], если встретим на ней занятую клетку, значит мы нашли брешь в диагонали через которую можно зайти и спуститься вниз.
Если дошли до верха возвращаемся в исходную точку (1012, y), дальше можем пытаться проверить так же спуск влево вниз. А если встретим нисходящую диагональ [\], будем достраивать ее в обратную сторону [\\].
В лучшем случае у нас будет либо снова брешь. Либо одна сплошная диагональ [//] или две сходящиеся диагонали [\\//] без понимания что под ними :)
Дальше можно разбивать половины диагонали пополам, отсекать ненужные части и искать брешь по другому алгоритму, но вполне возможно есть более оптимальный вариант :)
P.S. главное условие победы подойти к монстру снизу
За логарифмическое количество попыток путь находится. Спускаемся по среднему столбцу, пока не уткнемся. Исходя из локальной конфигурации 3х2, на определение которой нужно не больше двух попыток, можно либо понять, что мы нашли проход, либо узнать в левой или в правой части (либо в обеих) точно есть проход, тогда задача сводится к исходной, только с шириной в два раза меньше. Таким образом путь находится бинарным поиском.
либо в обеих
После проверки конфигурации проход есть только в одной части и вы не знаете в какой именно. Поэтому только бинарного поиска недостаточно.
Знаем в какой именно. Допустим у нас конфигурация, что закрашена клетка слева вверху от той, куда мы уперлись. Тогда у нас есть две области: слева вверху от конфигурации 2х2 из этих двух клеток и справа внизу. Для этих областей известен проход как к линии целиком над ними, так и выход с линии целиком под ними. Т.е. вопрос только в проходе через эти области, при этом для каждой области ситуация аналогична исходной. Очевидно, что проход точно есть в той области, где число столбов больше, чем число строк. Это условие будет всегда выполняться как минимум для одной из этих двух областей. Для конфигурации, когда закрашена клетка справа сверху, ситуация просто зеркальна.
Я ни разу не математик, но ради интереса задал эту задачку Sonnet 3.5. Она выдала решение за 10-15 секунд. Но правильное ли, мне не известно ? Но убедительно)
Давайте разберем эту геометрическую задачу шаг за шагом:
Сначала обозначим ключевые элементы:
ABC - треугольник, где AB < AC < BC
I - центр вписанной окружности ω
X - точка на BC, где прямая через X || AC касается ω
Y - точка на BC, где прямая через Y || AB касается ω
P - точка пересечения AI с описанной окружностью (кроме A)
K - середина AC
L - середина AB
Ключевое наблюдение: в треугольнике ABC, AI - биссектриса угла BAC.
Рассмотрим ∠KIL:
KI и LI - это медианы к сторонам AC и AB соответственно
∠KIL = 1/2 ∠BAC (так как AI - биссектриса)
Теперь рассмотрим ∠YPX:
AP - диаметр описанной окружности (так как AI ⊥ BC в треугольнике)
∠YPX вписанный, опирается на дугу YX
∠YPX = 1/2 ∠YAX (вписанный угол равен половине центрального)
Ключевой момент: ∠YAX = 180° - ∠BAC
Это следует из того, что YX || BC (поскольку Y и X выбраны так, что прямые через них параллельны сторонам треугольника)
Следовательно:
∠YPX = 1/2 (180° - ∠BAC) = 90° - 1/2 ∠BACТеперь сложим углы:
∠KIL + ∠YPX = 1/2 ∠BAC + (90° - 1/2 ∠BAC) = 90°Удваиваем обе части:
2(∠KIL + ∠YPX) = 180°Следовательно:
∠KIL + ∠YPX = 180°
Что и требовалось доказать.
Google DeepMind приблизился к решению задач высшего уровня математики