P9144 [THUPC 2023 Preliminary] The Final Event

Dear players of *La Lumière: Scarlet Intense Flame*: Thank you for your continuous support and love for *La Lumière: Scarlet Intense Flame*. We are very sorry to announce that *La Lumière: Scarlet Intense Flame* will stop operation services at 16:00 on March 5, 2023. The timetable related to the service shutdown is as follows: ……

The veteran anime-style mobile game *La Lumière: Scarlet Intense Flame* will stop operation services this March. As a loyal player of this game, Little S hopes to grind a special score in the game’s final event, so as to bring a perfect ending to the unforgettable time spent with this game over the past decade. Each event in *La Lumière: Scarlet Intense Flame* has its own unique rules, and the final event is Chase Festival. In Chase Festival, players repeatedly clear a randomly generated multi-layer maze. Each time the player exits the maze, the score for this randomly generated maze is settled independently based on the evaluations of monster kills on each layer. The process of each maze run is simplified as follows: 1. Choose the difficulty of the random maze to challenge. Little S is a veteran player, so in this problem we assume Little S always challenges the highest difficulty maze. The highest difficulty maze has at most $N$ layers. After the difficulty is determined, start from layer 1 of the randomly generated maze. 2. Challenge layer $i$. When challenging layer $i$, Little S may fail, succeed and obtain a normal evaluation, or succeed and obtain a high evaluation. If Little S chooses the conservative strategy, then the probabilities are: fail with probability $p_{i,0}$, succeed with a normal evaluation with probability $p_{i,1}$, and succeed with a high evaluation with probability $p_{i,2}$. If Little S chooses the aggressive strategy, then the probabilities are: fail with probability $q_{i,0}$, succeed with a normal evaluation with probability $q_{i,1}$, and succeed with a high evaluation with probability $q_{i,2}$. - With a normal evaluation, gain $s_{i,1}$ points on the current layer; with a high evaluation, gain $s_{i,2}$ points on the current layer. These points are **not added directly** to the player’s total score, but are **settled when exiting the maze**. If the challenge succeeds and the current layer is not the last one ($i

The first line contains three integers $N, M, c'$, where the meanings of $N$ and $M$ are the same as in the statement, and $c'=100c$. It is guaranteed that $1\le N\le 6$, $1\le M\le 10000$, $0\le c'\le 100$. In the next $N$ lines, each line contains eight integers $s_{i,1}, s_{i,2}, u_{i,0}, u_{i,1}, u_{i,2}, v_{i,0}, v_{i,1}, v_{i,2}$. Here, $s_{i,1}$ and $s_{i,2}$ denote the points corresponding to a normal evaluation and a high evaluation, respectively; $u_{i,j}$ and $v_{i,j}$ denote the probability weights of each outcome when using the conservative strategy and the aggressive strategy, respectively: $p_{i,j}=\dfrac{u_{i,j}}{u_{i,0}+u_{i,1}+u_{i,2}}$, $q_{i,j}=\dfrac{v_{i,j}}{v_{i,0}+v_{i,1}+v_{i,2}}$. It is guaranteed that $1\le s_{i,1}\le s_{i,2}\le 10000$, $0\le u_{i,j}, v_{i,j}\le 10000$, and $u_{i,1}+u_{i,2}\ge 1$, $v_{i,1}+v_{i,2}\ge 1$.

Output one line containing $M$ real numbers. The $i$-th real number ($1\le i\le M$) represents the maximum probability, under the optimal strategy, of being able to obtain exactly $i$ points when the remaining distance to the target score is exactly $i$ points. Your output is considered correct if the absolute error of each real number does not exceed $10^{-6}$ compared with the corresponding standard output.

#### Subtasks For $100\%$ of the testdata, it is guaranteed that $1\le N\le 6$, $1\le M\le 10000$, $0\le c'\le 100$, $1\le s_{i,1}\le s_{i,2}\le 10000$, $0\le u_{i,0}, u_{i,1}, u_{i,2}, v_{i,0}, v_{i,1}, v_{i,2}\le 10000$, and $u_{i,1}+u_{i,2}\ge 1$, $v_{i,1}+v_{i,2}\ge 1$. #### Notes *La Lumière: Scarlet Intense Flame 2* will meet everyone in the warm and blossoming season of spring 2023. #### Source From the preliminary round of the 2023 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2023). Solutions and other resources can be found at . Translated by ChatGPT 5