No.1457 Stop Deleting Your Tbeets Hard
タグ : / 解いたユーザー数 92
作問者 :
shiomusubi496
Note
This problem has a strict execution time limit, so using a fast language is recommended. (It has been confirmed that the writer's solution gets TLE in Python3 and AC in PyPy3.)
Problem Statement
Sushi Toruna-kun uses an SNS called $Tbutter$.
Currently, Sushi Toruna-kun has $N$ tbeets. The $i$-th tbeet of Sushi Toruna-kun has $A_i$ likes. Not wanting to become a Tbutter addict, Sushi Toruna-kun has decided to delete tbeets so that his number of tbeets becomes $M$ or less.
Since merely deleting tbeets would be boring, Sushi Toruna-kun also wants to make the average number of likes equal to $Z$.
Tbeets with $Y$ or fewer likes are boring, so Sushi Toruna-kun always deletes them. Tbeets with $X$ or more likes are interesting, so he cannot delete them. For all other tbeets, he may freely decide whether to delete them or not. However, at least $1$ tbeet must remain.
Output the number of ways in which the number of remaining tbeets is $M$ or less and the average number of likes is $Z$. However, if the number of tbeets cannot be made $M$ or less no matter how he deletes them, output Handicapped.
Input
$N\ M\ X\ Y\ Z$ $A_1\ A_2\ A_3\ ... A_N$
Constraints
$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$)
There exists at least $1$ index $i$ such that $Y < A_i$
All inputs are integers
Output
Depending on whether Sushi Toruna-kun can make his number of tbeets $M$ or less:
・if he cannot, print Handicapped;
・if he can, print the number of ways in which the number of remaining tbeets is $M$ or less and the average number of likes is $Z$,
on $1$ line. Print a newline at the end.
Sample
Sample 1
Input
9 6 8 2 7 1 3 2 5 4 7 6 8 9
Output
4
Tbeets with $8$ or more likes must be kept, so tbeets $8,9$ must be kept.
Also, tbeets $1,3$, which have $2$ or fewer likes, must be deleted.
In this case, the ways of keeping tbeets that satisfy the conditions are the following
- Keep tbeets $4,7,8,9$
- Keep tbeets $4,6,7,8,9$
- Keep tbeets $5,8,9$
- Keep tbeets $5,6,8,9$
Sample 2
Input
5 2 3 0 2 0 4 3 6 50
Output
Handicapped
All tbeets except tbeet $1$ must be kept, so the number of tbeets cannot be made $2$ or less.
Sample 3
Input
6 3 6 2 4 2 2 3 5 1 1
Output
1
It suffices to keep tbeets $3,4$.
Sample 4
Input
5 2 3 2 1 1 2 1 3 1
Output
0
If the number of tbeets can be made $M$ or less but the average cannot be made $Z$, output $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。