In a football championship, N teams are competing against each other on the league stage. The current number of points of each team are X1, X2, X3....XN. M days of league stage are remaining and on each day K teams win and each of the winning team's points is incremented by 1. Top B teams will qualify for the playoffs in the championship. Officials of the tournament want to how many teams have a non-zero probability of making it to the playoffs.
Note: If points of certain teams are equal, any of the teams can qualify for playoffs and each team has equal probability.
Input format
- The first line contains an integer T denoting the number of test cases. For each test case:
- The first line contains four space-separated integers N, M, K, and B.
- The second line contains N space-separated integers X1, X2, X3...XN.
Output format
Print T integers. For each test case:
- Print the number of teams that have a non-zero probability of making it to the playoffs.
Constraints
- \( 1\leq T \leq 20000\)
- \(1 \leq N \leq 200000\)
- \(1 \leq M \leq 10^9\)
- \(1 \leq B,K < N\)
- \( 1 \leq X_i \leq 10^9\)
- Sum of N over all test cases will not exceed 200000.
2 4 2 2 1 4 1 2 3 4 1 1 1 4 4 4 4
3 4
First test case: Only one team can make it to the playoffs, two days of league stage are left and 2 points on each day are to be gained. Every team has probablity to qualify for playoffs other than team with 1 point. Let us look at the scenarios:
Bold are those teams which we want to win:
Team with 4 points: [4,1,2,3] -> [5,2,2,3] -> [5,3,2,3]
Team with 1 points has no chance to qualify ( Zero probablity)
Team with 2 points: [4,1,2,3] -> [4,2,3,3] -> [4,3,4,3] (Any of the first or third team can qualify so probablity>0)
Team with 3 points: [4,1,2,3] -> [4,2,2,4] -> [4,3,2,5] 4th team has maximum points so they can be choosen in this case.
So all teams other than second have non-zero chance and also note that in case of ties you can qualify any team you want.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor