高坂さんと園田さんと南さんは子供の頃からの仲良し3人組だ。3人は沖縄に修学旅行に行くも、台風が来てしまい、海で遊ぶことができないのでババ抜きをすることにした。
園田さんは勝負事には強いが、ポーカーフェイスが苦手なため、自分のカードが引かれるときに無意識にかわいらしい顔芸を披露してしまう。園田さんを愛して止まない高坂さんと南さんは、園田さんの顔芸を見るだけで園田さんの手札が分かってしまうため、園田さんのカードを引くときは、自分が有利になるように引くことができる。 一方、高坂さんと南さんは特に顔芸をしたりはしないので、手札がばれることはない。 よって、高坂さんと南さんのカードを引く人はそれぞれ、高坂さんと南さんが持っているカードの中から等確率で1枚引く。
どう考えても不利な園田さんは、ババ抜きでなかなか勝てないことに違和感を覚えている。 使用するカードの種類数nと初期の手札が与えられたとき、園田さんが負けとならない確率を求めてあげよう。
高坂さん、園田さん、南さんの3人は、以下の状況でババ抜きを行う。
使用するカードの種類数nと3人の初期の手札が与えられたとき、園田さんが負けとならない確率を求めてあげよう。
入力は4行からなり、以下の形式で与えられる。
n m_1 c_{1,1} ... c_{1,m_1} m_2 c_{2,1} ... c_{2,m_2} m_3 c_{3,1} ... c_{3,m_3}
1行目にジョーカー以外のカードの種類数nが与えられる。 続く入力は3行からなり、2行目に高坂さんの手札、3行目に園田さんの手札、4行目に南さんの手札の情報が与えられる。 i+1 (1 ≤ i ≤ 3)行目では行頭に手持ちの枚数m_i、続けて手持ちのカードを表すm_i個の整数c_{i,j} (1 ≤ j ≤ m_i)が空白区切りで与えられる。 0はジョーカー、1からnはカードに書かれた整数を表す。
園田さんが負けとならない確率を1行に出力せよ。答えには10^{−6}を超える絶対誤差があってはならない。
1 1 1 3 0 1 1 1 1
0.0
高坂さんが南さんのカード1を引き、高坂さんと南さんは手札が空になる。 園田さんはどうしても勝つことはできない。
1 2 1 1 1 1 2 0 1
0.5
はじめの高坂さんのターンは、高坂さんの手札が既に空なので何もしない。次の園田さんのターンでは、園田さんは南さんの手札のうちそれぞれ0.5の確率でカード1かジョーカーを引く。カード1を引いたとき、園田さんの手札は空となり勝利する。一方ジョーカーを引いたときは、次の南さんのターンで、南さんは確実にカード1を引くので園田さんが負けとなる。
2 3 0 1 2 3 1 2 2 3 1 1 2
0.5
2 2 0 1 6 2 2 2 1 1 1 1 2
0.6666666667