Мінімальні Нарди
Уявіть собі просту версію гри в нарди під назвою "Мінімальні Нарди". У цій грі бере участь лише один гравець, який використовує одну кістку та одну шашку (фішку).
Ігрове поле складається з (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.