Background

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:

……

Problem Description

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<N$), go to step 3 to choose whether to continue; otherwise ($i=N$), exit the maze and go to step 4 for settlement.

   • If the challenge fails, the player is forced to exit the maze and goes to step 4.

3. If the current layer is not the last layer, the player may choose whether to continue to the next layer. If choosing to continue, return to step 2; otherwise, exit the current maze and go to step 4 for settlement.

4. Score settlement for this maze run: If the player is forced to exit due to failure, then no reward is obtained for the current layer, and the accumulated points from all previous layers in this maze run must be multiplied by the penalty coefficient $c$ (to make the final score an integer, the game sums the penalized points first and then takes the floor). Except for forced exit, if the player exits voluntarily or exits after clearing the maze, the player can obtain all unsettled points in full.

Little S’s target score is relatively large, so Little S needs to first grind the highest difficulty maze many times, and then, when close to the target score, choose relatively stable strategies based on the remaining points needed, to ensure that the final score at the end of the event reaches the target score exactly. Little S cannot program, so Little S came to you, hoping you can help compute the maximum probability of reaching the target score exactly when the remaining required score is between $1$ and $M$, by challenging the maze only according to the process above and using the best strategy.

Input Format

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 Format

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.

2 8 50
3 4 0 1 1 0 1 1
4 5 1 2 1 1 1 2

0.125000000000000000 0.140625000000000000 0.515625000000000000 0.564453125000000000 0.135009765625000000 0.328369140625000000 0.548858642578125000 0.625278472900390625

见附件中的 2.in

见附件中的 2.ans

Hint

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 https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5