問題一覧 > 通常問題

No.2389 Cheating Code Golf

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 58
作問者 : 👑 獅子座じゃない人 / テスター : cleantted PCTprobability Mizar 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 9742 / 自分の提出
問題文最終更新日: 2023-07-20 17:55:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 398 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。