Ставити чи не ставити
Олександр Чарльз МакМіллан захоплюється азартними іграми, і під час своєї останньої поїздки до казино він знайшов нову гру. Вона відбувається на лінійній послідовності квадратів, як показано нижче.
Фішка спочатку розміщується на квадраті "Початок". Гравець намагається перемістити фішку до квадрата "Кінець" через серію ходів, після чого гра завершується. У кожному ході підкидається монета: якщо випадає орел, фішка переміщується на один квадрат вправо, а якщо решка — на два квадрати вправо (якщо фішка знаходиться на один квадрат від квадрата "Кінець", вона просто переміщується до квадрата "Кінець"). На цьому етапі потрібно виконати будь-яку інструкцію на квадраті, на якому зупинилася фішка. Кожна інструкція є однією з наступних:
Переміститися вправо на n квадратів (де n — це деяке додатне ціле число)
Переміститися вліво на n квадратів (де n — це деяке додатне ціле число)
Пропустити хід
Немає інструкції
Після виконання інструкції хід закінчується і починається новий. Зверніть увагу, що фішка виконує інструкцію лише на квадраті, на якому вона зупинилася після підкидання монети. Якщо, наприклад, фішка зупиняється на квадраті, який вказує переміститися на 3 квадрати вліво, переміщення виконується, але інструкція на отриманому квадраті ігнорується, і хід закінчується. Азарт у цій грі полягає в наступному: маючи розкладку дошки та ціле число T, ви повинні зробити ставку на те, чи закінчиться гра протягом T ходів.
Після того, як Олександр втратив свою сорочку та кілька інших предметів одягу, він вирішив, що йому потрібна професійна допомога — не в подоланні своєї залежності від азартних ігор, а в написанні програми, яка допоможе вирішити, як робити ставки в цій грі.
Вхідні дані
Вхідні дані складатимуться з кількох задач. Перший рядок міститиме ціле число n, що вказує на кількість задач. Кожна задача складатиметься з двох рядків: перший міститиме два цілі числа m та T (1 ≤ m ≤ 50, 1 ≤ T ≤ 40), де m — це розмір дошки, виключаючи квадрати "Початок" і "Кінець", а T — цільова кількість ходів. Наступний рядок міститиме інструкції для кожного з m внутрішніх квадратів на дошці. Інструкції для квадратів будуть розділені одним пробілом, а інструкція для квадрата буде однією з наступних: +n, -n, L або 0 (цифра нуль). Перша вказує на переміщення вправо на n квадратів, друга — на переміщення вліво на n квадратів, третя — на пропуск ходу, а четверта вказує на відсутність інструкції для квадрата. Жодне переміщення вправо або вліво ніколи не виведе вас за межі дошки.
Вихідні дані
Вихідні дані для кожної задачі складатимуться з одного рядка, або
Ставте на. x.xxxx
якщо ви думаєте, що є більше ніж 50% ймовірності, що гра закінчиться за T або менше ходів, або
Ставте проти. x.xxxx
якщо ви думаєте, що є менше ніж 50% ймовірності, що гра закінчиться за T або менше ходів, або
Нічия. 0.5000
в іншому випадку, де x.xxxx — це ймовірність закінчення гри за T або менше ходів, округлена до 4 десяткових знаків. (Зверніть увагу, що через округлення обчисленої ймовірності для відображення, ймовірність 0.5000 може з'явитися після повідомлення Ставте на. або Ставте проти.).