No.2158 hibit Who Will Full-Solve X Days Later
タグ : / 解いたユーザー数 28
作問者 :
KowerKoint2010
/ テスター :
kotamanegi
hibit_at
Michirakara
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
-1on $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もしくは右上の雲マークをクリックしてアカウントを作成してください。