P8804 [Lanqiao Cup 2022 National B] Failure

In software or system development, we may encounter many kinds of failures. To infer the cause from the observed symptoms, engineers summarize a 2D table called a correlation matrix to describe the relationship between failure causes and failure symptoms. For example:  Each row represents a failure cause, and each column represents a failure symptom. The matrix indicates that cause $A$ may produce symptoms $2$, $3$, $4$, and cause $B$ may produce symptoms $1$, $3$. In real development, if a failure cause occurs, engineers can compute the probability of each cause based on the observed symptoms, and then check the causes in descending order of probability, so as to locate the cause quickly. Now assume that at any given time, only one failure cause can occur in the system, and for a given cause, the occurrences of different symptoms are independent events. For example: Assume the system is currently affected by cause $A$. There is a probability of $\frac{1}{3}$ that symptom $2$ occurs, a probability of $\frac{1}{4}$ that symptom $3$ occurs, and a probability of $\frac{1}{2}$ that symptom $4$ occurs. Since these $3$ symptoms occur independently, the probability that symptoms $2$, $3$, and $4$ occur at the same time is $\frac{1}{2 \times 3 \times 4}$. By convention, if there is no `x` mark in the correlation matrix, it means this failure cause will definitely not produce that symptom. For example, cause $A$ will definitely not produce symptom $1$. Based on historical experience testdata, we have obtained the probability of each failure cause occurring, as well as the probability of each symptom occurring under each failure cause. Now, given the symptoms currently observed in the system, find the probability that each failure cause has occurred.

Line $1$: Two positive integers $N, M$. $N$ is the number of failure causes (indexed $1 \ldots N$), and $M$ is the number of failure symptoms (indexed $1 \ldots M$). Line $2$: $N$ integers. The $i$-th number is the probability $P_{i}$ that failure cause $i$ occurs. Lines $3 \ldots N+2$: Each line contains $M$ integers. The integer in row $i+2$, column $j$ is $P_{i j}$, which represents the probability (percentage) that symptom $j$ occurs when failure cause $i$ occurs. Line $N+3$: One positive integer $K$, the number of symptoms that are currently observed. Line $N+4$: $K$ positive integers, the indices of the currently observed symptoms in order, with no duplicates.

Lines $1 \ldots N$: Output each failure cause and its probability in descending order of probability. If probabilities are the same, output the smaller-indexed cause first. The first number is the cause index, and the second number is the failure probability (percentage), rounded to $2$ decimal places.

For all test cases, $1 \leq N \leq 40, 1 \leq M \leq 20, 0 \leq P_{i} \leq 100, \sum\left(P_{i}\right)=100$, $0 \leq P_{i j} \leq 100$. Lanqiao Cup 2022 National Contest B Group, Problem G. Translated by ChatGPT 5