Минимальные нарды
Вам предлагается простая версия игры в нарды, известная как "Минимальные Нарды". В этой игре участвует один игрок, который использует одну кость и одну фишку.
Игровое поле состоит из (N+1) клеток, пронумерованных от 0 (старт) до N (финиш). Игра начинается с того, что фишка находится на старте (клетка 0). Цель игры — переместить фишку на финиш (клетка N). Фишка перемещается на количество клеток, выпавшее на кости. Кость выдает случайное число от 1 до 6 с равной вероятностью.
Фишка не может пересекать финиш. Если бросок кости приводит к тому, что фишка выходит за пределы финиша, она отступает на столько клеток, насколько было превышено. Например, если фишка находится на клетке (N−3), и выпадает "5", фишка перемещается на клетку (N−2), так как превышение составляет 2. В следующем ходе фишка продолжает движение к финишу как обычно.
Каждая клетка, кроме старта и финиша, может содержать одну из двух специальных инструкций.
Пропустить один ход (обозначено "L" на Рисунке 1). Если фишка останавливается здесь, вы не можете перемещать её в следующем ходе.
Вернуться к началу (обозначено "B" на Рисунке 1). Если фишка останавливается здесь, она возвращается на старт.
Дана конфигурация игрового поля (размер N и расположение специальных инструкций), необходимо вычислить вероятность успешного завершения игры за заданное количество ходов.
Входные данные
Входные данные состоят из нескольких наборов, каждый из которых содержит целые числа в следующем формате.
N T L B
Lose1
···
LoseL
Back1
···
BackB
N — это индекс финиша, который удовлетворяет 5 ≤ N ≤ 100. T — количество ходов, за которое нужно вычислить вероятность успеха. T удовлетворяет 1 ≤ T ≤ 100. L — количество клеток с инструкцией "Пропустить один ход", удовлетворяющее 0 ≤ L ≤ N−1. B — количество клеток с инструкцией "Вернуться к началу", удовлетворяющее 0 ≤ B ≤ N−1. Эти числа разделены пробелом.
Lose_i — индексы клеток с инструкцией "Пропустить один ход", удовлетворяющие 1 ≤ Lose_i ≤ N−1. Все Lose_i различны и отсортированы по возрастанию. Back_i — индексы клеток с инструкцией "Вернуться к началу", удовлетворяющие 1 ≤ Back_i ≤ N−1. Все Back_i различны и отсортированы по возрастанию. Ни одно число не встречается одновременно в Lose_i и Back_i.
Конец ввода обозначается строкой из четырех нулей, разделенных пробелом.
Выходные данные
Для каждого набора данных необходимо вывести вероятность успешного завершения игры за заданное количество ходов. Ошибка в выводе не должна превышать 0.00001.