Card Duel#4577
Two players are engaged in a card game. Initially, each player receives a certain number of cards, denoted as n_1 and n_2, respectively. During each turn, both players select one card from their hands and reveal it simultaneously. The player with the weaker card discards it, while the player with the stronger card retrieves theirs. If both cards are of equal strength, both are discarded. The game continues until at least one player has no cards left. If one player still has cards remaining, they earn point, while the other scores . If both players run out of cards, each scores points. There are different types of cards in total. The strength relationship between the cards is potentially non-transitive and is specified by the matrix . The element A_{ij} is if card defeats card , and otherwise. The goal is to calculate the maximum average score for the first player, assuming the second player plays optimally.
Constraints
1 \leq n_1, n_2, N \leq 8.
A_{ij} + A_{ji} = 1 for i \neq j, A_{ii} = 0.
The first line contains the number .
The next lines each contain numbers, defining the matrix .
The following line contains the number n_1 followed by n_1 numbers, each indicating the type of card for the first player.
The subsequent line provides the cards for the second player in the same format.
Output the value of the game for the first player with a precision of at least 10^{-8}.
Example 1