\input problem.tex
\def\probname{Codenames}
\def\probno{?}
\def \headeryear {2020/2021}
\fullheader
\par
Codenames is a popular board game. Two teams compete by each having a
``spymaster'' give one-word clues that can point to multiple words on
the board. The other players on the team attempt to guess their
team's words while avoiding the words of the other team. The
objective is to be the first team to have all their team's words
revealed.
\par
Players split into two teams: red and blue. One player of each team
is selected as the team's spymaster; the others are field operatives.
\par
$N$ Codename cards, each bearing a word, are laid out in a line. Each
word represents one of the following: a red agent, a blue agent, an
assassin, or an innocent bystander. All players can see all the
Codename words, but only the spymasters know the identities of the
cards.
\par
Teams take turns. On each turn, the appropriate spymaster gives a
verbal hint about the words on the respective cards. Each hint may
only consist of one single word and a number. The spymaster's hint
should be as close to their own agents' cards as possible. The hint's
number tells the field operatives the maximum number of guesses to
make.
\par
After a spymaster gives the hint, their field operatives make guesses
about which Codename cards bear words related to the hint and point
them out, one at a time. When a Codename card is pointed out, the
spymaster reveals the identity of that card---a blue agent card, a
red agent card, an innocent bystander card, or an assassin
card. Depending on the identity of the card, one of these things
happens:

{\parskip=0pt
\item{$\bullet$}If an assassin is pointed out, the game ends immediately, and their team loses.
\item{$\bullet$}If an innocent bystander is pointed out, the turn simply ends.
\item{$\bullet$}If an agent of the other team is pointed out, the turn ends, and that other team is one agent closer to winning.
\item{$\bullet$}If an agent of their team is pointed out, they are one agent closer to winning, and they may choose to make another guess.
}
\par
The game ends when all of one team's agents are identified (winning
the game for that team), or when one team has identified an assassin
(losing the game).
\par
To simplify the problem, let's assume that both teams share the same
dictionary of hint words and their associations with Codename
cards. For example, consider this board ($N = 6$):
\par
{\tt Plate}(R)\quad {\tt Screen}(I)\quad {\tt Novel}(A)\quad {\tt Robin}(B)
\quad {\tt Iron}(R)\quad {\tt Server}(B)
{\parskip=0pt \par
(R: Red team's agent; B: Blue team's agent; I: Innocent bystander; A: Assassin)}
\par
The list of hint words and their associated Codename cards are:
\smallskip
\hbox {\indent {
\vbox{\offinterlineskip
\hrule
\halign{&\vrule#&\strut\quad#\hfil\quad\cr
height2pt&\omit&&\omit&\cr
&{\tt Alfred}&&{\tt Robin, Server, Plate}&\cr
&{\tt Net}&&{\tt Server, Screen, Plate}&\cr
&{\tt Computer}&&{\tt Screen, Server}&\cr
&{\tt Twitter}&&{\tt Screen, Robin, Server}&\cr
&{\tt Crusoe}&&{\tt Robin, Novel}&\cr
&{\tt Film}&&{\tt Iron, Screen}&\cr
height2pt&\omit&&\omit&\cr}
\hrule}} \hfil}
\vfill \eject \continuedheader \par
Once the spymaster gives a hint word and a number, $K$ (an integer
between 1 and the number of unrevealed words associated with the hint), their field
operatives make random guesses---with equal probability---from the
list of associated words that are not revealed yet. They will
continue to make guesses until one of the following happens: (1) they
get $K$ hits, (2) they have won the game, or (3) their turn ends with
a miss. They will never make guesses outside the list or use hints
from the previous rounds. It is illegal for the spymaster to give a
hint word if all its associated Codename cards have already been
revealed. All hint words can be used multiple times by either team.
\par
For example, assuming the blue team goes first in the first round,
the blue spymaster may give a hint ``Twitter, 2''. The blue team has
$1/3$ chance of guessing ``Screen'', ``Robin'' and ``Server'',
respectively. If they happen to guess ``Screen'', their turn ends as
the word is an innocent bystander. Otherwise, they get a hit and will
make another guess, with $1/2$ chance on either of the remaining two
words. Regardless of the choice, their turn will end after this
guess, and the red team will start their team with the red spymaster
giving a hint.
\par
Now you are selected as the spymaster, and your team (color specified
in the input) goes first. Assuming both spymasters play optimally,
what is your probability of winning the game?
\par
The first line of input consists of an integer and a character,
separated by a single space. The integer is $N$ ($1 \le N \le 15$),
the size of the board. The character is {\tt R} or {\tt B},
indicating your team (red or blue).
\par
The second line consists of $N$ distinct words, separated by a single
space. Each word consists of up to 20 lowercase English letters.
\par
The third line consists of $N$ single-character strings, separated by
single spaces. The $i$-th string indicates the identity of the $i$-th
word, with the following meaning: {\tt R}---Red team's agent; {\tt
B}---Blue team's agent; {\tt I}---Innocent bystander; {\tt
A}---Assassin. There are one or more red team agent and blue team
agent words, and there are zero or more innocent bystander and
assassin words.
\par
The fourth line consists of an integer $M$ ($1 <= M <= 50$), which is
the number of hint words.
\par
Each of the following $M$ lines consists of an integer $H_i$ ($1 <=
H_i <= N$), followed by $H_i$ distinct words separated by single
spaces. It describes the associated Codename cards with the $i$-th
hint word. All words are guaranteed to appear on the board.
\par
Your program is to print the probability of winning the game. Your answer
will be considered correct if it has absolute error at most $10^{-4}$ with
judge data.
\vskip 22pt
\centerline {\it Sample Input}
\vskip 14pt
\:4 B
\:apple sleep java dog
\:B R I A
\:3
\:2 apple java
\:2 apple dog
\:2 sleep java
\vskip 22pt
\centerline{\it Output for the Sample Input}
\vskip 14pt
\:0.5000
\vfill \eject \continuedheader
\vskip \parskip
\centerline{\it Explanation for the Sample}
\par
The blue spymaster has three hint words to choose from (in any case,
their team can only make one guess in the turn, so the choice of $K$
does not matter): {\parskip=0pt
\item{1.} If they choose the first, their team has $1/2$ probability of guessing ``apple'' and winning the game, and $1/2$ probability of guessing ``java'' and ending the turn, which allows the red spymaster to give the third hint word and win. So the blue team's winning chance is $1/2$ in this case;
\item{2.} If they choose the second, their team has $1/2$ probability of guessing ``apple'' and winning the game, and $1/2$ probability of guessing ``dog'' and losing the game. So the blue team's winning chance is also $1/2$;
\item{3.} If they choose the third, their team has $1/2$ probability of
guessing ``sleep'' and losing the game, and $1/2$ probability of
guessing ``java'' and ending the turn, which allows the red spymaster to
give the third hint word and win. So the blue team's winning chance is
$0$ in this case.
\par}
\par
To sum up, the best strategy for the blue spymaster is either (1) or (2) and their winning chance is $1/2$.
\vfill \eject
\end
