問題一覧 > 通常問題

No.2158 X日後に全完するhibit君

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 28
作問者 : KowerKoint2010KowerKoint2010 / テスター : hibit_athibit_at kyskys MichirakaraMichirakara kotamanegikotamanegi
0 ProblemId : 8865 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-09 23:50:39

問題文

※実際の「あさかつ」では、AtCoder の過去問を難易度 (Difficulty)で $6$ つのグループに分け、その中からランダムに問題を出題しています。 ただし、直近 $60$ 日で出題された問題は抽選から外されます。 この問題では、これを一般化した問題セットのモデルを考えます。

$N$ 個のグループに分けられた問題があります。 $i$ 番目のグループには $P_i$ 個の問題があります。

$1$ 日に $1$ 度「あさかつ」が開催されます。$1$ 回のあさかつでは $N$ 個のグループから $1$ つずつ問題が抽選され、合計$N$ 個の問題が出題されます。 このとき、直近 $K$ 日以内に出題された問題は抽選から除外されます。

より厳密には、 $i$ 番目のグループの問題の集合を $A_i$ とし、 $i$ 番目のグループから $j$ 日目に出題される問題を $B_{i,j}$ とすると、 $j$ 日目に出題される問題の候補の集合 $S_{i,j}$ は $S_{i,j}=A_i\backslash\{B_{i,k}|k\in \mathbb{N},j-K\leq k\leq j-1\}$ と表されます。($\mathbb{N}$ は正の整数全体の集合、$X\backslash Y$ は集合 $X$ から集合 $Y$に 属する要素を取り去って得られる集合)

各グループから出題される問題の抽選は候補の中から等確率かつ独立に行われます。

hibit 君は、「あさかつ」に $1$ 日目から毎日参加します。

彼は毎日参加することでいつの日か全完したいと思っています。

全完とは、$60$ 分以内にその日の $N$ 問をすべて解くことを指します。 $60$ 分ちょうどで解ききった場合も全完になります。

hibit 君が $i$ 番目のグループの問題 $1$ つを解くのにかかる時間は $s_i$ 分ですが、 その問題が過去の「あさかつ」に出題されたことがある場合、代わりに $t_i$ 分で解くことができます。

hibit 君が初めて全完する日を $X$ 日目としたとき、 $X$ の最小値、最大値、期待値をそれぞれ求めてください。

入力

$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$)
  • 入力はすべて整数

出力

すべての抽選結果で hibit 君が全完することができる場合、$X$ の最小値、最大値、期待値を空白区切りでこの順に出力し、最後に改行してください。

期待値はジャッジ解との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正答とみなされます。

hibit 君が全完することができないのような抽選結果が $1$ 通りでも存在する場合、最小値、最大値、期待値を出力する代わりに

-1
と$1$ 行に出力してください。

サンプル

サンプル1
入力
2 1
3 20 10
2 50 45
出力
3 4 3.5

$1$ 日目に問題 $B_{1,1}$ と $B_{2,1}$ 、$2$ 日目に問題 $B_{1,2}$ と $B_{2,2}$ 、$3$ 日目に問題 $B_{1,1}$ と $B_{2,1}$ が出題されたとき、hibit 君は $3$ 日目に全完でき、これが最短です。

$1$ 日目に問題 $B_{1,1}$ と $B_{2,1}$ 、$2$ 日目に問題 $B_{1,2}$ と $B_{2,2}$ 、$3$ 日目に問題 $B_{1,3}$ と $B_{2,1}$ 、$4$ 日目に問題 $B_{1,2}$ と $B_{2,2}$ が出題されたとき、hibit 君は $4$ 日目に全完でき、これが最長です。

サンプル2
入力
2 1
2 60 40
2 60 40
出力
-1

この問題セットでは、hibit 君は永遠に全完することができません。悲しい。

サンプル3
入力
6 2
5 24 2
5 16 4
5 23 9
5 57 10
5 40 3
5 28 4
出力
4 12 6.5926641

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