No.1457 ツブ消ししとるなHard
タグ : / 解いたユーザー数 98
作問者 : sushitoruna / テスター : shiomusubi496
注意
この問題は実行時間制限が厳しいので高速な言語を使用することを推奨します。(writer解はPython3ではTLE、PyPy3ではACすることを確認しています。)
問題文
寿司取るな君は $Tbutter$ という SNS を利用しています.
現在, 寿司取るな君のツブート数は $N$ です. また, 寿司取るな君の $i$ ツブート目のいいね数は $A_i$ です. ツブ廃になりたくない寿司取るな君は, ツブ消しをすることでツブート数を $M$ 以下にすることにしました.
ただツブ消しするだけではつまらないので, 寿司取るな君はいいね数の平均を $Z$ にしようと思いました.
寿司取るな君は, いいね数が $Y$ 以下のツブートはつまらないので必ず消します. いいね数が $X$ 以上のツブートは面白いので消すことはできません. その他のツブートについては, 消すか消さないかを自由に決められます. ただし, ツブートは $1$ つ以上残すものとします.
残ったツブート数が $M$ 以下かつ, いいね数の平均が $Z$ になる場合の通り数を出力してください. ただし, どのようにツブ消しをしてもツブート数を $M$ 以下にできない場合は Handicapped
と出力してください.
入力
$N\ M\ X\ Y\ Z$ $A_1\ A_2\ A_3\ ... A_N$
制約
$1\leq M\leq N\leq 50$
$0\leq Y < X\leq 50$
$0\leq Z\leq 50$
$0\leq A_i\leq 50$ ($1 ≤ i ≤ N$)
$Y < A_i$ となる $i$ が最低 $1$ つは存在する
入力は全て整数
出力
寿司取るなくんがツブート数を $M$ 以下に
・できない場合はHandicapped
を
・できる場合は残ったツブート数が $M$ 以下かつ,いいね数の平均が $Z$ になる場合の通り数を
それぞれ $1$ 行に出力してください.最後に改行してください.
サンプル
サンプル1
入力
9 6 8 2 7 1 3 2 5 4 7 6 8 9
出力
4
$8$ いいね以上のものは必ず残さなくてはならないので $8,9$ ツブート目のツブートは必ず残さなければなりません.
また, $2$ いいね以下の $1,3$ ツブート目のツブートは必ず削除しなければなりません.
この時,条件を満たすツブートの残し方は
- $4,7,8,9$ ツブート目を残す
- $4,6,7,8,9$ ツブート目を残す
- $5,8,9$ ツブート目を残す
- $5,6,8,9$ ツブート目を残す
サンプル2
入力
5 2 3 0 2 0 4 3 6 50
出力
Handicapped
$1$ ツブート目を除いては必ず残さなくてはならないので, $2$ ツブート以下にすることはできません.
サンプル3
入力
6 3 6 2 4 2 2 3 5 1 1
出力
1
$3,4$ ツブート目を残せば良いです.
サンプル4
入力
5 2 3 2 1 1 2 1 3 1
出力
0
$M$ ツブート以下にはできるが平均を $Z$ にできないときは $0$ と出力してください.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。