Делать ставку или не делать ставку
Александр Чарльз МакМиллан обожает азартные игры, и во время своего последнего визита в казино он обнаружил новую игру. Она проводится на линейной последовательности квадратов, как показано ниже.
Фишка изначально находится на квадрате Start. Игрок должен переместить фишку на квадрат End, выполняя серию ходов, после чего игра завершается. В каждом ходе подбрасывается монета: если выпадает орел, фишка перемещается на один квадрат вправо, а если решка — на два квадрата вправо (если только фишка не находится в одном квадрате от квадрата End, в этом случае она просто перемещается на квадрат End). На каждом квадрате, на который попадает фишка, необходимо выполнить указанное действие. Каждое действие может быть одним из следующих:
Переместиться вправо на n квадратов (где n — некоторое положительное целое число)
Переместиться влево на n квадратов (где n — некоторое положительное целое число)
Пропустить ход
Нет указания
После выполнения указания ход заканчивается и начинается новый. Обратите внимание, что фишка следует указанию на квадрате, на который она попадает после подбрасывания монеты. Например, если фишка попадает на квадрат, который указывает переместиться на 3 клетки влево, перемещение выполняется, но указание на новом квадрате игнорируется, и ход заканчивается. Азартная игра заключается в следующем: зная расположение доски и целое число T, вы должны сделать ставку на то, завершится ли игра в течение T ходов.
После того как он проиграл свою рубашку и несколько других предметов одежды, Александр решил, что ему нужна профессиональная помощь — не в борьбе с его игровой зависимостью, а в создании программы, которая поможет ему решать, как делать ставки в этой игре.
Входные данные
Ввод состоит из нескольких экземпляров задачи. Первая строка содержит целое число n, указывающее количество экземпляров задачи. Каждый экземпляр состоит из двух строк: первая содержит два целых числа m и T (1 ≤ m ≤ 50, 1 ≤ T ≤ 40), где m — это размер доски, исключая квадраты Start и End, а T — целевое количество ходов. Следующая строка содержит указания для каждого из m внутренних квадратов на доске. Указания для квадратов разделены пробелом, и указание на квадрате может быть одним из следующих: +n, -n, L или 0 (цифра ноль). Первое указывает на перемещение вправо на n квадратов, второе — на перемещение влево на n квадратов, третье — на пропуск хода, а четвертое указывает на отсутствие указания для квадрата. Ни одно перемещение вправо или влево никогда не выведет вас за пределы доски.
Выходные данные
Вывод для каждого экземпляра задачи состоит из одной строки, либо
Bet for. x.xxxx
если вы считаете, что вероятность того, что игра закончится за T или менее ходов, больше 50%, либо
Bet against. x.xxxx
если вы считаете, что вероятность того, что игра закончится за T или менее ходов, меньше 50%, либо
Push. 0.5000
в противном случае, где x.xxxx — это вероятность того, что игра закончится за T или менее ходов, округленная до 4 десятичных знаков. (Обратите внимание, что из-за округления вычисленной вероятности для отображения вероятность 0.5000 может появиться после сообщения Bet for. или Bet against..)