問題一覧 > 通常問題

No.2158 hibit Who Will Full-Solve X Days Later

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : KowerKoint2010 / テスター : kotamanegi hibit_at kys Michirakara
お気に入りにしたユーザー ProblemId : 8865 / 自分の提出
問題文最終更新日: 2022-12-09 23:50:39
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 371 (Asakatsu Presents) (順位表) の他の問題:

Problem Statement

*In the actual "Asakatsu", past AtCoder problems are divided into $6$ groups by difficulty (Difficulty), and problems are chosen at random from those groups. However, problems given within the last $60$ days are excluded from the draw. In this problem, we consider a generalized model of this problem set.

There are problems divided into $N$ groups. The $i$-th group contains $P_i$ problems.

"Asakatsu" is held $1$ time per $1$ day. In $1$ session of Asakatsu, $1$ problem is drawn from each of the $N$ groups, so a total of $N$ problems are given. Here, problems given within the last $K$ days are excluded from the draw.

More strictly, let $A_i$ be the set of problems in the $i$-th group, and let $B_{i,j}$ be the problem given from the $i$-th group on day $j$. Then the set $S_{i,j}$ of candidate problems to be given on day $j$ is expressed as $S_{i,j}=A_i\backslash\{B_{i,k}|k\in \mathbb{N},j-K\leq k\leq j-1\}$. ($\mathbb{N}$ is the set of all positive integers, and $X\backslash Y$ is the set obtained by removing from set $X$ the elements belonging to set $Y$.)

The draw of the problem from each group is performed uniformly at random among the candidates and independently.

hibit participates in "Asakatsu" every day, starting from day $1$.

By participating every day, he hopes to achieve a full solve someday.

A full solve means solving all $N$ problems of that day within $60$ minutes. Finishing them in exactly $60$ minutes also counts as a full solve.

It takes hibit $s_i$ minutes to solve $1$ problem of the $i$-th group, but if that problem has been given in a past "Asakatsu", he can solve it in $t_i$ minutes instead.

Let day $X$ be the day on which hibit achieves a full solve for the first time. Find the minimum value, the maximum value, and the expected value of $X$.

Input

$N\ K$
$P_1\ s_1\ t_1$
$P_2\ s_2\ t_2$
$\vdots$
$P_N\ s_N\ t_N$
  • $1\leq N\leq 6$
  • $1\leq K\leq 4$
  • $K\lt P_i\leq 5$ ($1\leq i\leq N$)
  • $1\leq t_i\leq s_i\leq 60$ ($1\leq i\leq N$)
  • All inputs are integers.

Output

If hibit can achieve a full solve under every possible draw result, output the minimum value, the maximum value, and the expected value of $X$ in this order, separated by spaces, followed by a newline.

The expected value is considered correct if its absolute or relative error from the judge's solution is at most $10^{-6}$.

If there exists even $1$ draw result under which hibit cannot achieve a full solve, instead of the minimum value, the maximum value, and the expected value, output

-1
on $1$ line.

Sample

Sample 1
Input
2 1
3 20 10
2 50 45
Output
3 4 3.5

If on day $1$ problems $B_{1,1}$ and $B_{2,1}$, on day $2$ problems $B_{1,2}$ and $B_{2,2}$, and on day $3$ problems $B_{1,1}$ and $B_{2,1}$ are given, hibit can achieve a full solve on day $3$, and this is the earliest case.

If on day $1$ problems $B_{1,1}$ and $B_{2,1}$, on day $2$ problems $B_{1,2}$ and $B_{2,2}$, on day $3$ problems $B_{1,3}$ and $B_{2,1}$, and on day $4$ problems $B_{1,2}$ and $B_{2,2}$ are given, hibit can achieve a full solve on day $4$, and this is the latest case.

Sample 2
Input
2 1
2 60 40
2 60 40
Output
-1

With this problem set, hibit can never achieve a full solve. How sad.

Sample 3
Input
6 2
5 24 2
5 16 4
5 23 9
5 57 10
5 40 3
5 28 4
Output
4 12 6.5926641

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。