P3849 [TJOI2007] Football Lottery Betting

People who know football lotteries may be familiar with a game called “Win-Draw-Loss,” which means predicting the outcome of each match. Below are some terms related to Win-Draw-Loss. Note: each group is one valid combination of bets. Betting: the act of buying football lottery tickets with cash. Single bet: the bettor selects exactly one predicted result for every match. The number of bets (tickets) is 1. Multiple bet: the bettor selects two or more predicted results for some matches. The number of bets equals the number of combinations in the multiple bet. For example, if a bettor predicts two outcomes (e.g., win or draw) for one match, three outcomes (win, draw, loss) for another match, and exactly one outcome for all other matches, then the number of bets is $2 \times 3 = 6$. Such a multiple bet can be regarded as a set containing six single bets. In a typical Win-Draw-Loss game, the lottery operator specifies several matches within a round and asks bettors to predict each match’s result (win, draw, loss). The prize amount depends on how many matches the bettor predicts correctly.

We now consider a simplified model. In one round, the bettor needs to predict the results of $n$ matches. Each match’s win-draw-loss outcomes have probabilities $p(i, r)$. Here, $i$ denotes the $i$-th match and $r \in \{0, 1, 2\}$ denotes the home team’s loss, draw, and win, respectively. The value $p(i, r)$ is the probability that match $i$ ends with result $r$. In addition, $q(i, r)$ denotes the probability that, among all purchased bets, result $r$ is chosen for match $i$, i.e., the fraction of the total number of bets that select that outcome for that match. For example, if $q(1, 0) = 0.5$, then we know that $50\%$ of the bets choose the home team to lose in the first match. We assume these $n$ matches are independent, i.e., the outcomes $p(i, r)$ are independent across matches, and the selections $q(i, r)$ are also independent across matches (with $r \ne r'$). In this model, a ticket wins only if it correctly predicts all $n$ matches. The total prize pool is $M$ and is shared equally among all winning bets. Therefore, for a single bet $R_i = \{r_{i1}, r_{i2}, \ldots, r_{in}\}$, where $r_{ij}$ is the predicted result of bet $R_i$ for match $j$, its winning probability is: $$ P(R_i)=\prod\limits_{j=1}^n p(j, r_{ij}). $$ Let the total number of bets be $N$. Then the total number of winning bets is: $$ N \cdot Q(R_i)=N\cdot\prod\limits_{j=1}^n q(j, r_{ij}). $$ Hence, the expected prize (the average prize) received by bet $R_i$ is: $$ \dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i). $$ The above only considers single bets, i.e., the winning of a single $R_i$. For multiple bets, the situation is more complicated. A multiple bet is a set $R = \{R_1, R_2, \ldots, R_k\}$, where $k$ is the number of bets. For example, with three matches, if the first match is “win or loss,” the second is “draw,” and the third is “loss or draw,” then $k = 4$, and the set $R$ contains the following four elements: | | $r_{i1}$ | $r_{i2}$ | $r_{i3}$ | | ----- | -------- | -------- | -------- | | $R_1$ | 0 | 1 | 0 | | $R_2$ | 0 | 1 | 1 | | $R_3$ | 2 | 1 | 0 | | $R_4$ | 2 | 1 | 1 | In a multiple bet $R$, you win if at least one $R_i$ predicts all results correctly. Therefore, the expected prize of $R$ is: $$ \sum_{R_i\in R}\dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i). $$ The problem: given the information for $n$ matches (the probabilities of outcomes and the probabilities that bettors buy those outcomes), and the maximum number of bets $U$ allowed in a multiple bet, design a multiple betting scheme that does not exceed the maximum number of bets ($k \le U$) and maximizes the expected prize.

The first line contains four positive integers $n, N, M, U$, where $n, U \le 10^4$ and $N, M \le 10^9$. Each of the next $n$ lines contains six real numbers. The six real numbers on line $i + 1$ are $p(i, 0), p(i, 1), p(i, 2), q(i, 0), q(i, 1), q(i, 2)$, describing match $i$. Here, $p(i, 0) + p(i, 1) + p(i, 2) = 1$, $q(i, 0) + q(i, 1) + q(i, 2) = 1$, and $q(i, j) \ne 0$.

Output a real number, the natural logarithm of the maximum expected prize: $$ \ln \left( \operatorname{max}_{\lvert R \rvert \le U}\left\{\sum_{R_i\in R}\dfrac{M}{N\cdot Q(R_i)} \cdot P(R_i)\right\}\right). $$ Print the answer with $3$ decimal places (rounded half up).

Translated by ChatGPT 5