Problem:
 Score : 700 points    Problem Statement N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.  M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges,
and increase the score of each chosen problem by 1 .  After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset.
Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.  How many problems out of the given N have a chance to be chosen for the problemset?      Constraints  2 \le N \le 10^5  1 \le M \le 10^9  1 \le V \le N - 1  1 \le P \le N - 1  0 \le A_i \le 10^9         Input Input is given from Standard Input in the following format:  N  M  V  P  A_1  A_2  ...  A_N       Output Print the number of problems that have a chance to be chosen for the problemset.        Sample Input 1 6 1 2 2
2 1 1 3 0 2      Sample Output 1 5  If the only judge votes for problems 2 and 5 , the scores will be 2  2  1  3  1  2 .
The problemset will consist of problem 4 and one of problems 1 , 2 , or 6 .  If the only judge votes for problems 3 and 4 , the scores will be 2  1  2  4  0  2 .
The problemset will consist of problem 4 and one of problems 1 , 3 , or 6 .  Thus, problems 1 , 2 , 3 , 4 , and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.       Sample Input 2 6 1 5 2
2 1 1 3 0 2      Sample Output 2 3  Only problems 1 , 4 , and 6 have a chance to be chosen.       Sample Input 3 10 4 8 5
7 2 3 6 1 6 5 4 6 5      Sample Output 3 8

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while l+1 < r:
        i = (l+r) >> 1
        A = a[i]+m
        ri = bisect.bisect_right(a,A)
        j = n-ri
        if j >= p:
            l = i
            continue
        s = m*p
        for j in range(n-p+1):
            if i == j:
                continue
            s += min(m,A-a[j])
        if s >= m*v:
            r = i
        else:
            l = i
    print(n-r)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while l+1 < r:
        i = (l+r) >> 1
        A = a[i]+m
        ri = bisect.bisect_right(a,A)
        j = n-ri
        if j >= p:
            l = i
            continue
        s = m
        for j in range(n-p+1):
            if i == j:
                continue
            s += min(m,A-a[j])
        s += m*(p-1)
        if s >= m*v:
            r = i
        else:
            l = i
    print(n-r)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

def isOk(i):
    if i < P:
        return True

    b = A[i] + M
    if b < A[P - 1]:
        return False

    cnt = (P - 1) * M + (N - i) * M

    for a in A[P - 1: i]:
        cnt += max(0, b - a)
    return cnt >= M * V

ok = 0
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2

    if isOk(mid):
        ok = mid
    else:
        ng = mid
print(ng)

Solution (Python):
N, M, V, P = map(int, input().split())
A = sorted(map(int, input().split()))[::-1]
ans, s = P, A[P-1]
for i in range(P, N):
    if A[i]+M>=A[P-1]:
        ans += ((V+i+1-N-P)*M<=(i-P+1)*(A[i]+M)-s)
        s += A[i]
print(ans)

Solution (Python):
N, M, V, P = map(int, input().split())
*A, = map(int, input().split())
A.sort(reverse=True)

ans = P
s = A[P-1]
for i in range(P, N):
    if A[i]+M>=A[P-1]:
        a = V-(N-i+P-1)
        ans += (a*M<=(i-P+1)*(A[i]+M)-s)
        s += A[i]

print(ans)

Solution (Python):
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

def f(x):
  if x>=n-p:
    return 1
  elif a[x]+m<a[n-p]:
    return 0
  else:
    ct=(p-1)*m+m+x*m
    for i in range(x+1,n-p+1):
      ct+=a[x]+m-a[i]
    if ct>=m*v:
      return 1
    else:
      return 0

L=-1;R=n
while R-L>1:
  x=(L+R)//2
  if f(x)==1:
    R=x
  else:
    L=x
print(n-L-1)

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, V, P = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype = np.int64)

A.sort()
r = N
l = 0
border = N - P
AP = A[border]
B = AP - A
np.cumsum(B, axis = 0, out = B)

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	tmp += (ind + P) * M
	tmp += B[border] - B[ind]
	tmp += (score_border - A[border]) * (border - ind)
	if tmp >= M * V:
		return 1
	else:
		return 0

while r - l > 1:
	mid = (r + l) // 2
	if solve(mid):
		r = mid
	else:
		l = mid

if solve(l):
	print(N - l)
else:
	print(N - r)

Solution (Python):
n,m,v,p = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse = True)

ans = p-1

d = 0

for i in range(p-1,n):
    if A[p-1] > A[i] + m:break
    may = (p-1 + n-i-1)*m
    may +=(A[i]+m)*(i - p+1) - d
    ans += (may + m>= m*v)
    d += A[i]

print(ans)

Solution (Python):
def solve(mid):
    if mid <= p:
        return True
    max_ = a[mid - 1] + m
    b = [max_ - a[i] for i in range(p - 1, mid - 1)]
    new_v = v - p - n + mid
    
    
    if min(b) < 0:
        return False
    if new_v <= 0:
        return True

    cnt = 0
    for num in b:
        cnt += min(num, m)
    return cnt >= m * new_v
       


n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)

ok = 1
ng = n + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, m, v, p = map(int, readline().split())
a = np.array(read().split(), np.int64)
a.sort()


def check(i):
    if n - i <= p:
        return True
    x = a[i] + m
    y = np.zeros(n, np.int64)
    y = x - a
    y = np.minimum(y, m)
    y[n - p + 1:] = m
    if (y < 0).any():
        return False
    y[i] = 0
    next = y.sum()
    return next >= m * (v - 1)


low = -1
high = n - 1
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid):
        high = mid
    else:
        low = mid
print(n - high)

Solution (Python):
import sys
input = sys.stdin.readline

def judge(x):
    if N-P<=x<=N-1:
        return True
    if A[x]+M<A[N-P]:
        return False
    
    cnt = 0
    
    for i in range(N-P+1):
        if i==x:
            continue
        
        cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*(V-P)

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

print(N-binary_search())

Solution (Python):
import sys
input = sys.stdin.readline

def judge(x):
    if N-P<=x<=N-1:
        return True
    if A[x]+M<A[N-P]:
        return False
    
    cnt = 0
    
    for i in range(N):
        if i>=N-P+1:
            cnt += M
        else:
            cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*V

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

print(N-binary_search())

Solution (Python):
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok(x):
        if x <= P-1:
            return True
        elif A[x-1] + M < A[P-1]:
            return False

        votes = M*(P-1 + N-x) + M
        for i in range(P-1, x-1):
            votes += A[x-1] + M - A[i]
        if M*V <= votes:
            return True
        else:
            return False

    def binary_search_meguru():
        ng = N+1
        ok = -1
        while abs(ok - ng) > 1:
            mid = ng + (ok - ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Solution (Python):
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

def ok(x):
    if x == -1:
        return False
    if x >= n-p:
        return True
    cnt = 0
    for i in range(x+1, n-p):
        cnt += max((A[x]+m)-A[i], 0)
    cnt += m*x
    cnt += m*(p-1)
    if max(m*(v-1) - cnt, 0)+A[n-p] <= A[x]+m:
        return True
    else:
        return False

l = -1
r = n-1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(n-r)

Solution (Python):
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

def ok(x):
    if x == -1:
        return False
    if x >= n-p:
        return True
    cnt = 0
    for i in range(x+1, n-p):
        cnt += max((A[x]+m)-A[i], 0)
    cnt += m*x
    cnt += m*(p-1)
    if max(m*(v-1) - cnt, 0)+A[n-p] <= A[x]+m:
        return True
    else:
        return False

l = -1
r = n-1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(n-r)

Solution (Python):
import sys
input = sys.stdin.readline

n, m, v, p = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
a = a[::-1]

ans = p

b = a[p:]
b_cumsum = [a[p - 1]]
for i in b:
    b_cumsum.append(b_cumsum[-1] + i)

for i in range(len(b)):
    vote_cnt = max(0, (v - p - (len(b) - (i + 1)))) 
    if b_cumsum[i] + m * vote_cnt <= (b[i] + m) * (i + 1) and a[p - 1] <= b[i] + m: 
        ans += 1
    else:
        break

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, m, v, p = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
a = a[::-1]

ans = p

b = a[p:]
b_cumsum = [a[p - 1]]
for i in b:
    b_cumsum.append(b_cumsum[-1] + i)

for i in range(len(b)):
    vote_cnt = max(0, (v - p - (len(b) - (i + 1))))
    if b_cumsum[i] + m * vote_cnt <= (b[i] + m) * (i + 1) and a[p - 1] <= b[i] + m:
        ans += 1
    else:
        break

print(ans)

Solution (Python):
N,M,V,P=map(int, input().split())
*A,=map(int, input().split())

A.sort()
Ax = A[-P]  

def f(i):
    mine = A[i] + M 
    if mine < Ax: return False 
    votes = M*V
    votes -= M 
    votes -= min(P-1, V) * M 
    votes -= sum([min(mine - A[j], M) for j in range(N-P+1) if i!=j]) 
    if votes > 0 : return False 
    return True

under = -1
r = N-P
while r-under>1:
    m = (r+under)//2
    if f(m): r=m
    else: under=m

print(N-r)

Solution (Python):
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[max(0, P - 1): i]]

    if not B:
        return True
    cnt = sum(B) + (P - 1) * M + (N - i) * M
    return min(B) >= 0 and cnt >= M * V

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid
print(ng)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    B = A[N - P]
    low, high = -1, N
    while high - low > 1:
        mid = (low + high) // 2
        if mid >= N - P: high = mid
        elif A[mid] + M < B: low = mid
        else:
            border = A[mid] + M
            room = 0
            for i in range(N - P + 1):
                if i != mid: room += min(M, max(0, border - A[i]))
            if room >= max(0, V - P) * M: high = mid
            else: low = mid
            
    print(N - high)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def check_pickedup(N: int, M: int, V: int, P: int, A: list, accum_score: list, i: int) -> bool:
    th_score = A[P-1]
    if A[i] >= th_score:
        return True
    sum_surplus = (accum_score[i-1] - (accum_score[P-2] if P-2 >=0 else 0)) - ((i-1)-(P-2))*A[i]
    
    
    
    
    if th_score - A[i] <= M and sum_surplus <= M*(N-V):
        return True
    return False

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    
    accum_score = [A[0]] * N
    for i in range(1, N):
        accum_score[i] = accum_score[i-1] + A[i]
    
    
    ans = 0
    was_checked = {}
    for i, a in enumerate(A):
        
        if a in was_checked:
            ans += 1
            continue
        if check_pickedup(N, M, V, P, A, accum_score, i):
            ans += 1
            was_checked[a] = True
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10




def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p - 1, x):
            tmp += t - a[i]
        return tmp >= m * v
        
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys

def f(x):
    if a[x]+m<a[p-1]: return 0
    elif v<=p+n-1-x: return 1
    able=(p+n-1-x)*m
    able+=sum([a[x]+m-a[k] for k in range(p-1,x)])
    if able>=m*v: return 1
    else: return 0

n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>0:
    if r-l==1 and f(l)==1 and f(r)==0: break
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(l+1)

Solution (Python):

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    l = 0
    r = N - P + 1
    while l != r:
        k = (l + r)//2
        m = P * M + k * M
        t = A[k] + M
        if t < A[N - P]:
            l = k + 1
            continue
        for i in range(k+1, N-P+1):
            m += t - A[i]
        if m < M * V:
            l = k + 1
        else:
            r = k
    return N - r
print(main())

Solution (Python):
def judge(a, acc, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m + (a[i-1] + m)*(i - p) - (acc[i-2] - acc[p-2])
    return check >= m*v

n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)
acc = [0] * (n+1)
for i in range(n):
    acc[i] = a[0] if i == 0 else a[i] + acc[i-1]
ng = n + 1
ok = 0

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, acc, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1]
    return check >= m*v

n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)
ng = n + 1
ok = 0

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1]
    return check >= m*v

n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse=True)
ng = n + 1
ok = -1

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    N, M, V, P = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())), reverse=True)
    def ss(k):
        t = A[k] + M
        if A[P - 1] > t:
            return False
        r = M * (V - (N - k) - (P - 1))
        for i in range(P - 1, k):
            r -= min(M, max(0, t - A[i]))
            if r <= 0:
                return True
        return False
    return binsearch(P - 1, N, ss) + 1


print(main())

Solution (Python):
import sys
class IoTool:  
    DEBUG = 0
    def _reader_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _reader_oj():  
        return iter(sys.stdin.read().split('\n'))
    reader = _reader_dbg() if DEBUG else _reader_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

def main():
    n, m, v, p = map(int, input().split())
    val = list(map(int, input().split()))
    val.sort(reverse=True)
    ans, presum, v = p, val[p-1], v-p+1
    for i in range(p, n):
        if val[i] + m < val[p-1] or (val[i] + m)*(i-p+1) - presum < m*(v-1-(n-i-1)):
            break
        presum += val[i]
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N, M, V, P = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)


def is_possible(idx):
    if idx < P:
        return True
    if A[P - 1] <= A[idx]:
        return True
    if A[idx] + M < A[P - 1]:
        return False
    t = P * M
    for i in range(P - 1, idx):
        t += A[idx] + M - A[i]
    for i in range(idx + 1, N):
        t += M
    if t < M * V:
        return False
    return True


left, right = 0, N
while left + 1 < right:
    middle = (left + right) // 2
    if is_possible(middle):
        left = middle
    else:
        right = middle
print(right)

Solution (Python):
N, M, V, P = map(int, input().split())
A = sorted([int(x) for x in input().split()], reverse=True)

def func():
    S = 0
    c = 0
    for i in range(P-1, N):
        if A[i] + M >= A[P-1] and (V - (P-1) - (N-i-1) - 1) * M <= S + (A[i] + M - A[P-1]) * c:
            pass
        else:
            return i
        S += A[P-1] - A[i]
        c += 1
    return N
print(func())

Solution (Python):
n,m,v,p = map(int, input().split())
al = list(map(int, input().split()))
al.sort(reverse=True)

def check(x):
    if x<p:
        return True
    if al[p-1]>al[x]+m:
        return False

    s = 0
    for i in range(n):
        if i<p-1:
            s += m
        elif p-1<=i<x:
            s += al[x]+m-al[i]
        else:
            s += m
    return s>=m*v

ok = -1
ng = n
while ng-ok>1:
    mid = (ok+ng)//2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)

Solution (Python):
import bisect
n,m,v,p=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
ok=n
ng=-1
def solve(x):
    if bisect.bisect_right(l,l[x])>=n-p+1:
        return 1
    lx=l[x]+m
    lxi=bisect.bisect_right(l,lx)-1
    if lxi<=n-p-1:
        return 0
    
    f=0
    for i in range(n):
        if i<=x or i>n-p:
            f+=m
            continue         
        else:
            f+=min(lx-l[i],m)
    if f>=v*m:
        return 2
    else:
        return 0

    
while ok-ng>1:
    x=(ok+ng)//2
    if solve(x):
        ok=x
    else:
        ng=x
    
print(n-ok)

Solution (Python):
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
p = A[P-1]


def f(X):
    x = A[X]
    if x + M < p: return False
    votes = M*V
    votes -= M * (P-1)
    for i in range(P-1,N):
        votes -= min(M, x + M - A[i])
    return votes <= 0

ok = 0
over = N
while over - ok > 1:
    mid = (over + ok) // 2
    if f(mid): ok = mid
    else: over = mid
print(ok+1)

Solution (Python):


N,M,V,P = map(int, input().split())

A = list(map(int, input().split()))


A.sort(reverse=True)
ok = P-1
"""
indexはN-1までなので、ngはN-1の気がするのだが......
[ok,ng)か？
*****  okは条件を満たす（選ばれうる）し、ngは条件を満たさない（選ばれない）ので、ng=N-1とすると、そこを最初からきりすててしまうから！  *****
最終的なokとngの境界で選ばれるか選ばれないか分かれ、境界の先は単調に選ばれうる
"""
ng = N 
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= M*V:
        ok = mid
    else:
        ng = mid

print(ok + 1)

Solution (Python):


N,M,V,P = map(int, input().split())

A = list(map(int, input().split()))


A.sort(reverse=True)
ok = P-1
ng = N 
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= M*V:
        ok = mid
    else:
        ng = mid

print(ok + 1)

Solution (Python):
import sys
from bisect import bisect

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    border = A[N - P]

    low, high = -1, N
    while high - low > 1:
        mid = (low + high) //2
        point = A[mid] + M
        if point < border: low = mid
        elif mid >= N - P: high = mid
        else:
            space = (mid + P) * M
            for i in range(mid + 1, N - P + 1 ): space += point - A[i]
            if space >= M * V: high = mid
            else: low = mid
    print(N - low - 1)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()

    h, l = N, -1
    b = A[N - P]
    while h - l  > 1:
        m = (h + l) // 2
        NG = A[m] + M
        if NG < b: l = m
        elif m >= N - P: h = m
        else:
            room = (m + P) * M
            for i in range(m + 1, N - P + 1): room += NG - A[i]
            if room < M * V: l = m
            else: h = m

    print(N - l - 1)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if n-ri >= p:
            l = i
            continue
        cnt = 0
        for j in range(n-p+1):
            if i == j:
                continue
            cnt += min(m,aim-a[j])
        if cnt >= m*(v-p):
            r = i
        else:
            l = i
    print(n-r)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if n-ri >= p:
            l = i
            continue
        cnt = 0
        for j in range(n-p+1):
            if i == j:
                continue
            cnt += min(m,max(0,aim-a[j]))
        if cnt >= m*(v-p):
            r = i
        else:
            l = i
    print(n-r)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
"""
AtCoder Grand Contest 041  B - Voting Judges


N個の問題があり、M人がそれぞれV問に１点足していく。同じ人が同じ問題に点は入れられない。
全員が点を入れた後、得点の大きいものからP個選ばれる。
選ばれうる可能性のある問題の個数を考える。

例えば1,2,3,4,5,6,7,8,9,10として、３人が４問に加点するのを考える。その後４問が選ばれるとする
５がえらばれうるか考えてみる。
５に３点入れて、残りは５未満に足しておけば８に並ぶので選ばれうる。
上位一位にいくより上位４位にはいる方が縛りが緩そう。１～４のどこにいてもいいので。

なので、とりあえず４位になることを目標とする。
４位になるには上位３位の10,9,8には負けててもいいが、少なくとも７に並ぶ必要がある。
また、投票者が３人なので、多くても＋３しかされない。

とりあえず５にとって最善の＋３した場合を考える。
このときに７に＋２とか６に＋３とかされて８を上回られると選ばれない。
なので、５的には、自分に最大に点を割り振って、残りは順位に影響ないところで使いつぶすのが嬉しい。

１～４について、＋３しても順位に影響ないから、これらには割り振る。
８～１０についても、５的には４位に入ることができたら問題ないので、これらについても＋３して問題ない。
ついで、６，７であるが、これが９になると５は勝てないので、こいつらには＋した結果でも８にとどまってほしい。

こんな感じで、P位になるためにある数字に最大に割り振って、残りを使いつぶす。
で、全体でM*V点持っていて、使いつぶしたときにこれを使い切っていなければ、今回でいうところの６とか７に振るしかなくなる。
そのときは選ばれる可能性がない。
みたいな？

"""
import bisect


N,M,V,P = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

l = P - 1
r = N
while r - l > 1:
    mid = (l + r) // 2

    curr_max = A[mid] + M
    if curr_max < A[P-1]:
        r = mid
        continue

    cnt = 0
    
    for i in range(P-1, N):
        if i == mid:
            continue
        
        cnt += min(M, max(0, curr_max - A[i]))

    
    if cnt >= M * (V - P):
        l = mid
    else:
        r = mid


print(l + 1)

Solution (Python):
N, M, V, P = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
As = [0]*(N+1)
for i in range(N):
    As[i+1] = A[i] + As[i]

ans = 0
b = A[N-P]
for i in range(N):
    if b-A[i] > M:
        continue
    if P+i>=V:
        ans += 1
    else:
        r = As[N-P+1]-As[i+1]-A[i]*(N-P-i)
        if r <= (N-V)*M:
            ans += 1

print(ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.read
N, M, V, P, *A = map(int, read().split())

A = np.array(A + [10 ** 10], np.int64)
A.sort()
A = A[::-1]
left = P
right = N + 1

while right - left > 1:
    mid = (right + left) // 2
    score = A[mid] + M
    if score < A[P]:
        right = mid
        continue

    s = np.minimum(score - A[P:], M)
    if np.sum(s) >= M * (V - (P - 1)):
        left = mid
    else:
        right = mid

print(left)

Solution (Python):
import sys

read = sys.stdin.read
N, M, V, P, *A = map(int, read().split())

A += [10 ** 10]
A.sort(reverse=True)
left = P
right = N + 1

e = tuple(enumerate(A))
while right - left > 1:
    mid = (right + left) // 2
    score = A[mid] + M
    if score < A[P]:
        right = mid
        continue
    s = M * (V - P)
    for idx, i in e[P:]:
        if mid == idx:
            continue
        if i + M <= score:
            s -= M
        else:
            s -= score - i

    if s <= 0:
        left = mid
    else:
        right = mid

print(left)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, v, p = LI()
A = LI()
A.sort()
def bi(x):
    if A[x] + m < A[-p]:
        return 0
    if x + p >= v:
        return 1
    ret = (x + p) * m
    l = x + 1
    r = n - p + 1
    for i in range(l, r):
        ret += A[x] + m - A[i]
        if ret >= v * m:
            return 1
    return 0


ok = n - p
ng = -1
while ok > ng + 1:
    mid = (ok + ng) // 2
    if bi(mid):
        ok = mid
    else:
        ng = mid


print(n - ok)