Вежливый близорукий пьяный бот на минном поле

11

Как следует из названия, эта проблема наполовину вдохновлена вежливым близоруким пьяным ботом @NP

Наш бедный бот помещается на декартовой сетке в начале координат, и через каждую минуту он перемещается на 1 единицу в одном из четырех направлений (вверх, вниз, влево, вправо).

Через n минут все скрытые мины в сетке активируются, убивая любого плохого бота, который может оказаться над ними. Мины расположены во всех целочисленных координатах, удовлетворяющих уравнению | y | = | x |.

Вызов

Вам будет предоставлено n , количество минут до взрыва мины, в качестве входных данных и выходных данных вы должны найти вероятность того, что бот мертв .

Ввод : натуральное число, представляющее n .

Вывод : Пусть вероятность того, что бот мертв, будет p / q, где p и q - относительно простые целые числа (q не может быть 0, но p может). Выход р.

правила

  • Ваш алгоритм не должен работать в экспоненциальном или более высоком времени. В идеале он должен работать за полиномиальное время или меньше.
  • Ваш алгоритм должен быть способен обрабатывать входные данные n<20 (могут быть скорректированы, если слишком сложно) в разумные сроки.
  • Это вызов .
  • Перебор всех возможностей для данного n будет определенно не принят в качестве ответа.

Тестовые случаи

1->0

2->3

4->39

6->135

8->7735

10->28287

Пример расчета для n = 6

У нас есть 4 возможных хода: U, D, R и L. Общее количество путей, которое можно было бы выбрать, составляет 4 ^ 6 или 4096. Есть 4 возможных случая, которые приземляются вдоль линии y = x: x, y = ± 1; х, у = ± 2; х, у = ± 3; или x = y = 0. Мы посчитаем количество способов попасть в (1,1), (2,2) и (3,3), умножим их на 4, чтобы учесть другие квадранты, и добавим это количество способов в конечном итоге в (0,0).

Случай 1: бот заканчивается в (3, 3). Чтобы бот оказался здесь, у него должно было быть 3 правильных хода и 3 хода вверх. Другими словами, общее количество способов попасть сюда - это способы перестановки букв в последовательности RRRUUU, в которой 6 выбирают 3 = 20.

Случай 2: бот заканчивается в (2,2). Чтобы бот оказался здесь, у него могло быть 2 хода вверх, 3 хода вправо и 1 ход слева; или 2 правильных движения, 3 движения вверх и 1 движение вниз. Таким образом, общее количество способов получить здесь является суммой способов перестановки букв в последовательностях RRRLUU и UUUDRR, обе из которых (6 выбирают 1) * (5 выбирают 2) = 60, всего 120 возможностей ,

Случай 3: бот заканчивается в (1,1). Чтобы бот оказался здесь, у него могли быть: 1 правильный ход, 3 хода вверх и 2 хода вниз. В этом случае количество способов перестановки букв в последовательности RUUUDD составляет (6 выберите 1) * (5 выберите 2) = 60.

1 ход вверх, 3 движения вправо и 2 движения влево. В этом случае количество способов перестановки букв в последовательности URRRLL составляет (6 выберите 1) * (5 выберите 2) = 60.

2 движения вправо, 1 движение влево, 2 движения вверх и 1 движение вниз. В этом случае количество способов перестановки букв в последовательности UUDRRL составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

Таким образом, общее количество способов попасть в (1,1) составляет 300.

Случай 4: бот заканчивается в (0,0). Чтобы бот оказался здесь, он мог иметь:

3 правых хода и 3 левых хода. В этом случае количество способов перестановки букв в последовательности RRRLLL составляет (6 выберите 3) = 20.

3 ходов вверх и 3 ходов вниз. В этом случае количество способов перестановки букв в последовательности UUUDDD составляет (6 выберите 3) = 20.

1 движение вправо, 1 движение влево, 2 движения вверх и 2 движения вниз. В этом случае количество способов перестановки букв в последовательности RLUUDD составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

1 движение вверх, 1 движение вниз, 2 движения вправо и 2 движения влево. В этом случае количество способов перестановки букв в последовательности RRLLUD составляет (6 выберите 1) * (5 выберите 1) * (4 выберите 2) = 180.

Таким образом, общее количество способов попасть в (0,0) составляет 400.

Сложив эти случаи вместе, мы получим, что общее число способов попасть в | y | = | х | 4 (20 + 120 + 300) + 400 = 2160. Таким образом, наша вероятность составляет 2160/4096. Когда эта доля полностью уменьшена, это 135/256, поэтому наш ответ 135 .

Дон Тысяча
источник
Мне нравится задача, но я думаю, что было бы полезно включить работающий пример для одного из очень маленьких тестовых случаев (например, 2 или 3).
Мистер Кскодер
@ Mr.Xcoder Я добавлю один, когда у меня будет время.
Дон Тысяча
2
Интересный вызов. Обратите внимание, что использование слова «идеально» в правиле делает его не правилом. Было бы полезно сказать определенно так или иначе.
Трихоплакс
1
Но никто не говорит об алгоритме обучения первого поколения?
Программы
1
@RedwolfPrograms ахаха, да, но у этого бота более клевое имя
Дон Тысяча

Ответы:

17

Python 2 , 65 байт

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Попробуйте онлайн!

Вероятность смерти бота может быть выражена как:

f(n)=2ss2, where s=12n(nn/2)

и бином понимается равным когда не является целым.0n/2

Мы можем рассуждать так. Какова вероятность того, что бот приземлится на линию ? Это происходит, если общее количество ходов вверх и влево равно общему количеству ходов вниз и вправо. Это та же вероятность, что, скажем, вы подбрасываете монету раз и получаете столько хвостов, сколько и голов. Вы должны выбрать сальто, чтобы быть главами сальто, что может быть сделано способами, из возможных последовательностей в целом, давая вероятностьy=xnn/2n(nn/2)2n

s=12n(nn/2)

Вероятность посадки линии также равна . Таким образом, вероятность посадки на любой линии равна сумме этих или , за исключением того, что мы дважды учитываем вероятность посадки в обеих линиях и должны вычесть ее, чтобы компенсировать.y=xs2sx=y=0

Оказывается, вероятность посадки на составляет всего , произведение вероятности посадки на каждой линии. Мы можем утверждать, что события независимы следующим образом: если мы выберем случайную последовательность равных чисел «Вверх или Влево» и «Вниз или Вправо», чтобы попасть на а также с «Вверх или Вправо» и «Вниз или Влево» «для мы можем однозначно объединить их в последовательность вверх, вниз, влево, вправо, взяв пересечение пар направлений в каждой позиции.x=y=0s2x=yx=y

Таким образом, вероятность посадки на или равна .x=yx=y2ss2

Код вычисляет бином используя это выражение как с базой . Чтобы извлечь числитель из доли вероятности, отметим, что знаменатель является степенью 2, поэтому мы используем выражение, чтобы разделить максимальную степень 2 , выраженную в виде классического битового трюка .(nn/2)(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Решение заключается в том, чтобы записать как чтобы на ссылались только один раз, и работать без дробей чтобы оставаться в целых числах. Вычисление имеет полиномиальное время по даже с использованием метода вычисления биномов.2ss21(1s)2s1/2nn


После написания доказательства вероятности смерти бота я нашел более чистый способ доказать это и представить его.

Будем отслеживать значения и после каждого хода бота. Каждое из четырех направлений вверх, вниз, влево и вправо либо увеличивает, либо уменьшает каждое из и , причем четыре направления соответствуют четырем комбинациям.a=x+yb=xyab

Таким образом, случайный ход эквивалентен случайному добавлению к и независимо к . Это равносильно выполнению отдельных случайных прогулок по и .a ± 1 b a b±1a±1bab

Теперь робот заканчивается на линии или именно тогда, когда или . Таким образом, вероятность завершения с равна и аналогично для . Поскольку прогулки независимы, вероятность того, что и равна , поэтому вероятность того, что хотя бы один равен нулю, является дополнением .x = - y a = 0 b = 0 a = 0 s = 1x=yx=ya=0b=0a=0 b=0a0b0(1-с)21-(1-с)2s=12n(nn/2)b=0a0b0(1s)21(1s)2

XNOR
источник
3
Фантастика! Я ждал кого-то, чтобы получить это. Я не представлял, что это так быстро. Недостатком является то, что большинству других ответов не нужно будет слишком много думать :(. Отлично +1
Дон Тысяча
наслаждайся маленькой щедростью (особо не жалко)
Дон Тысяча
1
@RushabhMehta Спасибо, это очень мило с вашей стороны! Ваша щедрость побудила меня написать более ясное доказательство, о котором я подумал позже.
xnor
Истинным источником вдохновения для этой проблемы была AIME I 2014 года проблема 11, если вы хотите проверить это.
Дон Тысяча