Почему я не могу решить UVa 12293 с помощью рекурсии?
Описание:
Есть две одинаковые коробки.
В одном из них находится n шаров, а в другом - один шар.
Алиса и Боб изобрели игру с коробками и шарами, в которую играют следующим образом:
Алиса и Боб ходят поочередно, Алиса ходит первой.
Для каждого хода игрок обнаруживает, что в коробке меньше шаров, и опустошает эту коробку (шары внутри будут удалены навсегда) и перераспределяет шары в другой коробке. После перераспределения в каждом ящике должен быть хотя бы один мяч.
Если игрок не может выполнить правильный ход, он проигрывает. Типичная игра показана ниже:
(5,1) -> (2,3) -> (1,2) -> (1,1)
Боб -> Алиса -> Боб -> Алиса
Когда оба ящика содержат только один шар, Боб не может больше ничего делать, поэтому Алиса выигрывает.
Вопрос: если Алиса и Боб оба достаточно умны, кто победит? Предположим, они оба очень умны и всегда следует безупречной стратегии.
Прежде всего, я подумал, что это рекурсивная проблема, поскольку вам нужно разделить ящик с наибольшим количеством шаров на два.
Такой как:
def rec(N):
if N%2:
return rec(N//2+1)+1
else:
return 1
Это соответствует данным Sample Inputs, которые равны '2, 3, 4, 0'.
Но в результате получился WA, я был очень сбит с толку, так как БУКВАЛЬНО перевел его.
Итак, я немного искал, похоже, ответы в Интернете были идентичны.
Все они решают ее по одному и тому же шаблону.
if n==2^i-1:
Bob wins.
else:
Alice wins.
Хм, это звучит разумно и получил AC от этого, но я все еще не понимаю - почему мое рекурсивное решение неверно?
После некоторого сравнения я обнаружил, что результат был другим для некоторых конкретных чисел, таких как «9, 11».
Поскольку это не числа 2^i-1, результатом должно быть «Алиса».
Но вот что делает мое решение.
(9,1) -> (5,4) -> (3,2) -> (2,1) -> (1,1)
Bob -> Alice -> Bob -> Alice -> Bob
(11,1) -> (6,5) -> (3,3)
Bob -> Alice -> Bob
Есть ли что-нибудь, что меня не волновало?