Как решить эту задачу?

Question

[kolomiec_artiom]

Два игрока играют в следующую игру. В координатном пространстве стоит фишка. В начале игры фишка находится в точке с координатами (0, 0, 0). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y, z) в одну из трёх точек: (x+3, y, z+2), (x, y+3, z+1), (x+1, y+2, z).

Игра заканчивается, когда расстояние от фишки до начала координат станет не меньше числа 5*sqrt(5).

Выигрывает тот игрок, который сделал последний ход.

а) Кто выигрывает при правильной игре?

б) Какое максимальное количество ходов может понадобиться этому игроку для выигрыша в правильной игре?

Answer 1

[longclaps]

nxt = [((0, 0, 0),)]
while nxt:
    cur, nxt = nxt, []
    for path in cur:
        x, y, z = path[-1]
        targets = [(a, b, c) for a, b, c in ((x + 3, y, z + 2),
                                             (x, y + 3, z + 1),
                                             (x + 1, y + 2, z))
                   if a * a + b * b + c * c < 125]
        if targets:
            for abc in targets:
                nxt.append(path + (abc,))
        else:
            print(*[(u - a, v - b, w - c) for (a, b, c), (u, v, w)
                    in zip(path, path[1:])])

Comments

[jcmvbkbc]

как этот код отвечает хотя бы на один поставленный вопрос?

[longclaps]

jcmvbkbc, этот код исчерпывающе отвечает хотя бы на один поставленный вопрос (на самом деле на оба).

[jcmvbkbc]

этот код исчерпывающе отвечает

-- Кто выигрывает при правильной игре? -- тот игрок, который сделал последний ход.
-- Какое максимальное количество ходов может понадобиться этому игроку для выигрыша в правильной игре? -- некоторое максимальное количество.

-- примерно так он отвечает.

[longclaps]

jcmvbkbc, неправда. Выигрывает 2й игрок. За 2 хода. По набору возможных траекторий видно, что при любом (из всего-то трёх) первом ходе первого игрока у второго есть выигрышое продолжение.