Warrior Lady

"Killers of Three Kingdoms" is a popular role playing card game designed with the novel Romance of the Three Kingdoms.

The game has four kinds of "Equipment Card": "Armour", "Weapon", "+1 horse", "-1 horse". Each player has an equipped-item area to hold equipments. A player is allowed to own only one of each of these 4 equipments in the equipped-item area. Equipments can be replaced by one of the same kind. However, after the replacement, the previous ones would be discarded. For simplicity, cards not belong to equipment (tool cards, basic cards and so on) are united as "Other Card" ignoring their functions in this problem.

Sun Shangxiang(Nickname: Xiangxiang), the lady with bow and arrows, is one of the favorable characters in this game. Her 2nd character ability - "Warrior Lady" (枭姬xiāo jī in Chinese) is described below:

Whenever an equipped card is discarded from the equipped-item area, Xiangxiang can immediately draw 2 cards from the deck. Note that Xiangxiang cannot voluntarily remove her equipped items. She can only replace them.

Now it is Xiangxiang’s turn. She has a certain amount of cards of each kind in her hand and her equipped-item area is empty. Given the number of cards of each kind in the deck, assume that every card in the deck will be taken with equal probability, and Xiangxiang will always equip the "Equipment Card" once she gets it. What is the expected number of cards Xiangxiang can draw in her action phase?

In the first line there is an integer T, indicates the number of test cases. (T <= 100)

For each case, two lines are given. The first line describes Xiangxiang’s hand cards, 5 integers indicating the number of "Armour", "Weapon", "+1 horse", "-1 horse" and "Other Card" respectively. The second line describes the cards in the deck which has the same format as above. The sum of the 10 integers is no more than 104.

For each case, output "Case k: v" on a single line, in which k is the case number, v is the maximum expected number of cards Xiangxiang can draw round to 2 digits after decimal point.

3

2 0 0 0 0
0 0 0 0 1

0 0 0 5 0
0 0 0 0 9

0 0 0 2 0
0 0 0 1 2

Case 1: 1.00
Case 2: 8.00
Case 3: 2.67

Case 1: Xiangxiang will stop drawing cards when the deck cards are used up.
Case 2: Xiangxiang cannot voluntarily remove her equipped items but replace them, so 5 equipments of the same kind can
only give her (5 – 1) * 2 = 8 cards.
Case 3: The probability to draw 3 cards is 2/3, and the probability to draw 2 cards is 1/3. So the answer is 3 * (2/3)
+ 2 * (1/3) = 8/3.

HongShu@UESTC

HDOJ 5th Anniversary Contest