J :: Videopoker

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Videopoker is the slot machine variant of the currently immensely popular game of poker. It is a variant on draw poker. In this game the player gets a hand consisting of five cards randomly drawn from a standard 52-card deck. From this hand, the player may discard any number of cards (between 0 and 5, inclusive), and change them for new cards randomly drawn from the remainder of the deck. After that, the hand is evaluated and the player is rewarded according to a payout structure. A common payout structure is as follows:

http://sharecode.ir/assets/problem_images/1458_a43dcfee4df40e3fd01792d573787402.jpg

Once you know the payout structure, you can determine for a given hand which cards you must change to maximize your expected reward. We’d like to know this expected reward, given a hand.

 

Poker hand rankings

For those of you not familiar with the game of poker, here follow explanations of the different poker hand rankings:

  • “one pair”consists of two cards of the same rank and three unmatched cards, e.g. Ah As Tc 8h 2c;
  • “two pair” consists of two cards of the same rank, two cards of a different same rank and an unmatched card, e.g. Ah As Th Ts 3c;
  • “three of a kind” consists of three cards of the same rank and two unmatched cards, e.g. Kc Kh Ks 6c 5s;
  • a “straight” consists of five cards of sequential rank in more than one suit, e.g. Jd Ts 9c 8d 7h. The ace can be used as low or high card, so straights from ace to five and from ten to ace can be formed;
  • a “flush” consists of five cards of the same suit, that are not in sequential rank, e.g. Ks Qs 8s 5s 3s;
  • a “full house” consists of three cards of the same rank and two cards of a different same rank, e.g. Js Jh Jc 4s 4c;
  • “four of a kind” consists of four cards of the same rank and an unmatched card, e.g. 7h 7c 7s 7d 5c;
  • a “straight flush” consists of five cards that form both a straight and a flush and that is not a royal flush, e.g. 7h 6h 5h 4h 3h;
  • a “royal flush” consists of five cards that form both a straight from ten to ace and a flush, e.g. As Ks Qs Js Ts.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

  • One line with nine integers xi (0 <= xi <= 1 000) describing the payout structure. The numbers are in increasing order and describe the payout for one pair, two pair, etc, until the royal flush.
  • One line with one integer n (1 <= n <= 10): the number of starting hands to follow.
  • n lines, each describing a starting hand. A hand consists of five space separated tokens of the form Xs, with X being the rank (‘2’ . . . ‘9’, ‘T’, ‘J’, ‘Q’, ‘K’ or ‘A’) and s being the suit (‘c’, ‘d’, ‘h’ or ‘s’).

Output

Per testcase:

One line for each starting hand with a floating point number that is the maximal expected reward for that hand. These numbers must have an absolute or relative error less than 10^−6.

Sample Input

1
1 2 3 4 5 10 25 100 250
5
Ah Ac Ad As 2s
Ks Qs Js Ts 2h
Ks Qs 2d 2h 3s
2d 4h 5d 3c 9c
2h 3h 6d 8h Tc

Sample Output

25.000000
8.9574468
1.5467160
0.9361702
0.6608135
Submit

Source: Northwestern European 2008