P15841 [Bulgarian NOI 2024] Fair / Fair

Felicia Day likes playing DnD. For this, she needs various $N$-sided dice. But she is a bit short on money, so to save some, she bought $K$ dice during a sale. However, she found that not all dice are fair (a die is fair if and only if each face has the same probability of appearing). More precisely, each die is fair with probability $P$; if it is unfair, then the probability of each face is generated as follows: 1. For $i$ from $1$ to $N$, generate a random number between $0$ and $1$, denoted as $Q_i$. 2. The probability that face $i$ appears equals $\frac{Q_i}{Q_1 + Q_2 + \cdots + Q_N}$. We can view a fair die as a die where all $Q_i$ values are equal. Felicia is eager to determine which dice are fair and which are not, but time is limited, so she rolled each die $M$ times. She recorded the results, that is, how many times each face appeared for each die, but she is not sure how to analyze this data. Please write a program to help her classify the dice as “fair” or “unfair”. Of course, 100% correctness is not required. Instead, each mistake will be penalized: if you classify a fair die as unfair, the penalty is $X$; if you classify an unfair die as fair, the penalty is $Y$. Your goal is to minimize the total penalty.

Read $N$, $M$, $P$, $X$, and $Y$ from the first line of standard input. The next line contains $K$. In the following $K$ lines, each line contains $N$ integers: the $j$-th number on the $i$-th line indicates the number of times face $j$ appeared on the $i$-th die.

For each die, output on a separate line in standard output 1 if you classify it as a fair die, or 0 if you classify it as an unfair die.

### Sample 1 Explanation It turns out that this solution classifies dice $2$ and $3$ correctly, but misclassifies dice $1$ and $4$. The penalty from the first mistake is $0.35$, and the penalty from the second mistake is $0.65$. The total penalty is $1.0$. ### Constraints - $2 \le N \le 8$ - $15 \le M \le 40$ - $0.5 \le P \le 0.8$ - $0.3 \le X, Y \le 0.7$ - $X + Y = 1$ - $K = 100000$ ### Scoring Each test point is scored independently. The score for a given test point is computed as follows: 1. Let $\text{TP}$ be the total penalty value of the mistakes made by your solution. 2. $\text{AP} = \frac{\text{TP}}{K}$ 3. $\text{BAP} = \min(P \times X,\ (1 - P) \times Y)$ 4. $S = \max\left(\frac{\text{BAP} - \text{AP}}{\text{BAP}},\ 0\right)$ 5. $R = \frac{S}{S_{\text{Author}}}$ 6. Your score is: $$ \begin{cases} 0.3 + 0.7 \times \left(1 - \left(1 - \frac{R - 0.8}{1 - 0.8}\right)^{0.75}\right) & \text{if } R \ge 0.8 \\ \frac{0.3}{0.8} \times R & \text{if } R < 0.8 \end{cases} $$ Translated by ChatGPT 5