No.2389 Cheating Code Golf
タグ : / 解いたユーザー数 58
作問者 : 👑
cleantted
PCTprobability
amentorimaru
Problem Statement
In the VR Code Golf Contest, participants submit program source code for each of $N$ problems and compete on the shortness of the source code that correctly solved each problem.
In this contest, up to $M$ incorrect submissions are allowed in total across all problems. Once the total number of incorrect submissions exceeds $M$, no further submissions can be made to any problem.
Also, a problem that has already been solved correctly cannot be resubmitted.
If a problem is solved correctly with source code of $x$ characters, the submitter earns a score of $\frac{1}{x}$, regardless of the number of incorrect submissions made to that problem.
Hitsuji-kun has decided to cheat in this contest by using randomization.
For the $i$-th problem $(1≤i≤N)$, Hitsuji-kun has source code of $A_i$ characters that does not use randomization and is correct with probability $1$, and source code of $B_i$ characters that uses randomization and is correct with probability $\frac{1}{P_i}$.
Here, whether code using randomization is judged correct or incorrect is determined independently for each submission. Also, the result (correct or incorrect) can be checked after every $1$ submission.
Find the expected value of the total score obtained when the source code to submit is decided successively so as to satisfy the following conditions.
- All problems can be solved correctly even if all submissions using randomization turn out to be incorrect.
- Among the ways satisfying the above, the expected value of the total score obtained is maximized.
Input
$N\ M$ $A_1\ B_1\ P_1$ $A_2\ B_2\ P_2$ $\vdots$ $A_N\ B_N\ P_N$
- All inputs are integers.
- $1\leq N\leq 12$
- $0\leq M\leq 40$
- $1\leq A_i\leq 10^6$
- $1\leq B_i\leq 10^6$
- $1\leq P_i\leq 10^6$
Output
Output the expected value of the total score obtained.
Sample
Sample 1
Input
3 1 8 2 3 8 6 2 8 8 2
Output
0.506944444444444
It is optimal not to use randomization on problem $3$, and for the other problems, to solve them in the order of problem $1$ and then problem $2$, using randomization until randomization fails $1$ time.
In this case, the possible scenarios are: randomization succeeds on both problem $1$ and problem $2$; randomization succeeds on problem $1$ and fails on problem $2$; and randomization fails on problem $1$ and is not used on problem $2$.
The probability that randomization succeeds on both problem $1$ and problem $2$ is $\frac{1}{P_1P_2}=\frac{1}{6}$, and in this case the score is $\frac{1}{B_1}+\frac{1}{B_2}+\frac{1}{A_3}=\frac{19}{24}$.
The probability that randomization succeeds on problem $1$ and fails on problem $2$ is $\frac{1}{P_1}\left(1-\frac{1}{P_2}\right)=\frac{1}{6}$, and in this case the score is $\frac{1}{B_1}+\frac{1}{A_2}+\frac{1}{A_3}=\frac{3}{4}$.
The probability that randomization fails on problem $1$ and is not used on problem $2$ is $1-\frac{1}{P_1}=\frac{2}{3}$, and in this case the score is $\frac{1}{A_1}+\frac{1}{A_2}+\frac{1}{A_3}=\frac{3}{8}$.
Therefore, the expected value of the total score obtained is $\frac{1}{6}\cdot\frac{19}{24}+\frac{1}{6}\cdot\frac{3}{4}+\frac{2}{3}\cdot\frac{3}{8}=0.506944444444444\ldots$.
Sample 2
Input
3 0 8 2 3 8 6 2 8 8 2
Output
0.375
Sample 3
Input
10 40 100 200 6 200 100 10 100 50 30 300 400 2 150 200 3 1000 200 6 200 1000 6 100000 100 6 100 100000 6 100 200 100000
Output
0.0845021746904274
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。