Участник:Danillich/ReachingPoints

Материал из DISCOPAL
Перейти к: навигация, поиск

Простое и понятное решение:

class Solution(object):
    def reachingPoints(self, sx, sy, tx, ty):
        def solve(tx, ty):    
            if (tx < sx) or (ty < sy):
                return False
            if tx==sx:
                if (ty-sy)%sx==0:
                    return True
                else:
                    return False
            if ty==sy:
                if (tx - sx)%sy == 0:
                    return True
                else:
                    return False
            return solve(tx - ty, ty) | solve(tx, ty - tx)
        return solve(tx, ty)

В данном случае задача делится на подзадачи: из каждой точки можно попасть только в две следующие. Решение сводится к рекурсивному поиску подходящих точек внутри прямоугольника, заданного значениями sx, sy, tx, ty.

На самом деле есть ощущение, что эту задачу можно решить без рекурсии и циклов, задав пару формул. Дело в том, что достигаемые из (sx, sy) точки укладываются на прямых вида y = x + b. Причем мной проверено, что для прямой с заданным b периодичность появления точек будет равна b - 1, если число b - 1 является линейной целочисленной комбинацией sx, sy, если нет, то точек на прямой не наблюдается.

Если этого того стоит, то можно попробовать оформить эти идеи в решение. Кажется, что получится крайне эффективно как по времени, так и по памяти, но времени на саму задачу потребуется немало.