P3239 [HNOI2015] King Arthur

Xiao K was accidentally brainwashed by the LL cult, to the extent that he even wants to quit the King Arthur cult. He decides to play one last game of King Arthur before quitting. Since it is the final battle, it must look good. As is well known, King Arthur is a game of luck, and the activation of skills is probabilistic. As an unlucky player (slang “African”), and also a former OIer, Xiao K naturally wants to maximize the expected damage dealt. But he has not coded for many years and cannot even code Splay correctly, so he hopes you can help him experience what it is like to be “European” (i.e., lucky). In this problem we consider a simplified model of the game. The player has a deck of $n$ cards. During the game, the player arranges the $n$ cards in some order, and after arranging, numbers the cards from front to back as $1 - n$. In this problem, the order is already fixed, which is the input order. Each card has a skill. The activation probability of the $i$-th card’s skill is $p_i$, and if it successfully activates, it deals $d_i$ damage to the opponent. Only by activating the skill can a card deal damage to the opponent. Considering practical factors and Xiao K’s “African” luck, $p_i$ is neither $0$ nor $1$, i.e., $0 < p_i < 1$. A game consists of $r$ rounds. In each round, the system starts from the first card and considers each card in order. In one round, for each card considered in order: 1. If this card has already activated its skill in this game, then 1.1. If this card is not the last one, skip it (consider the next card); otherwise (it is the last one), end this round. 2. Otherwise (this card has not activated its skill in this game), let this card be the $i$-th card. 2.1. Attempt to activate its skill with probability $p_i$. 2.2. If the skill activates, deal $d_i$ damage to the opponent and end this round. 2.3. If this card is already the last one (i.e., $i$ equals $n$), end this round; otherwise, consider the next card. Please help Xiao K compute the expected damage this deck can deal in one game.

The first line of the input file contains an integer $T$, representing the number of testdata groups. Then there are $T$ groups of data. The first line of each group contains two space-separated integers $n$ and $r$, representing the number of cards and the number of rounds in the game, respectively. Then follow $n$ lines, each containing a real number and an integer separated by a space, describing one card. The two numbers on the $i$-th line are $p_i$ and $d_i$, representing the activation probability (real number) of the $i$-th card’s skill and the damage (integer) dealt when the skill activates. It is guaranteed that $p_i$ has at most $4$ decimal places and is a valid probability.

For each group of data, output one line containing a real number, which is the expected damage dealt by this deck in one game. For each output line, your output will be judged correct only if its relative error with the standard answer does not exceed $10^{-8}$—i.e., $\frac{|a-o|}{a} \leq 10^{-8}$ (where $a$ is the standard answer and $o$ is your output). It is recommended to output $10$ decimal places.

There are $13$ possible cases: 1. In round $1$, card $1$ activates; in round $2$, card $2$ activates. Probability is $0.15$, damage is $5$. 2. In round $1$, card $1$ activates; in round $2$, card $3$ activates. Probability is $0.315$, damage is $3$. 3. In round $1$, card $1$ activates; in round $2$ no skill activates. Probability is $0.035$, damage is $2$. 4. In round $1$, card $2$ activates; in round $2$, card $1$ activates. Probability is $0.075$, damage is $5$. 5. In round $1$, card $2$ activates; in round $2$, card $3$ activates. Probability is $0.0675$, damage is $4$. 6. In round $1$, card $2$ activates; in round $2$ no skill activates. Probability is $0.0075$, damage is $3$. 7. In round $1$, card $3$ activates; in round $2$, card $1$ activates. Probability is $0.1575$, damage is $3$. 8. In round $1$, card $3$ activates; in round $2$, card $2$ activates. Probability is $0.04725$, damage is $4$. 9. In round $1$, card $3$ activates; in round $2$ no skill activates. Probability is $0.11025$, damage is $1$. 10. In round $1$ no skill activates; in round $2$, card $1$ activates. Probability is $0.0175$, damage is $2$. 11. In round $1$ no skill activates; in round $2$, card $2$ activates. Probability is $0.00525$, damage is $3$. 12. In round $1$ no skill activates; in round $2$, card $3$ activates. Probability is $0.011025$, damage is $1$. 13. In round $1$ no skill activates; in round $2$ no skill activates. Probability is $0.001225$, damage is $0$. The expected damage is the sum of the products of probabilities and corresponding damages, which is $3.266025$. Constraints: For all testdata, $1 \leq T \leq 444， 1 \leq n \leq 220， 0 \leq r \leq 132， 0 < p_i < 1， 0 \leq d_i \leq 1000$. Unless otherwise specified in the remarks, the $p_i$ and $d_i$ in the testdata are randomly generated. Please be aware of possible floating-point precision issues and take appropriate measures. This problem uses `special_judge`. Translated by ChatGPT 5