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):

import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0

    cumsum = [0 for i in range(N+1)]
    for n in range(N-1):
        cumsum[n+1] = A[n] + cumsum[n]

    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * (P-1)
            if affords <= 0:
                result += 1
                continue
            
            sunmmation = A[n] * (n-P) + M * (n-P) - (cumsum[n] - cumsum[P])
            affords -= sunmmation
            affords -= (N-n) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    V = int(next(tokens))  
    P = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()

Solution (Python):
def func(a, idx, m, v, p):
    if len(a) - idx <= p:
        return True
    if a[idx] + m < a[-p]:
        return False
    lim = 0
    for i in range(len(a)):
        if i <= idx:
            lim += m
        elif i <= len(a)-p:
            lim += a[idx] + m - a[i]
        else:
            lim += m
    if lim >= m*v:
        return True
    else:
        return False

def main():
    n, m, v, p = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    L, R = -1, n-1
    while L+1 < R:
        P = (L+R)//2
        if func(a, P, m, v, p):
            R = P
        else:
            L = P
    print(n-R)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():

    N, M, V, P = geta(int)
    A = [-10**15] + list(geta(int))
    A.sort()

    target = A[N - P + 1]

    def c(x):
        """
        return True iff Problem x has chance to be chosen 
        """
        if x >= N - P + 1:
            return True

        v_left = M * max(V - x - P + 1, 0)

        Ax = A[x] + M
        if Ax < A[N - P + 1]:
            return False

        ok = False
        for i in range(x + 1, N - P + 1 + 1):
            ad = min(M, Ax - A[i])
            v_left -= ad
            if v_left <= 0:
                ok = True
                break

        return ok

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

    print(N - right + 1)


if __name__ == "__main__":
    main()

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

a.sort(reverse=True)

higher = a[p-1]
for i in range(p,n):
    if(a[i] == a[i-1]):
        higher += a[i]
        continue

    if(a[p-1]- a[i] > m):
        print(i)
        exit()

    if(higher - a[i]*(i-p+1) > min(n-v,i-p+1)*m):
        print(i)
        exit()

    higher += a[i]

print(n)

Solution (Python):










import sys
readline = sys.stdin.readline

N,M,V,P = map(int,readline().split())
A = sorted(list(map(int,readline().split())),reverse = True)


border = A[P - 1]



ok = -1
ng = N

def isOk(x):
  
  if (x + 1) <= P:
    return True
  if A[x] + M < border:
    return False
  
  base = A[x] + M
  
  
  vote = (P - 1) * M
  
  for i in range(P - 1,len(A)):
    limit = max(base - A[i], 0)
    can = min(limit, M)
    vote += can
  if vote >= M * V:
    return True
  return False

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

Solution (Python):










import sys
readline = sys.stdin.readline

N,M,V,P = map(int,readline().split())
A = sorted(list(map(int,readline().split())),reverse = True)


border = A[P - 1]



ok = -1
ng = N

def isOk(x):
  

  if (x + 1) <= P:
    return True
  if A[x] + M < border:
    return False
  
  base = A[x] + M

  
  
  vote = (P - 1) * M

  
  for i in range(P - 1,len(A)):
    limit = max(base - A[i], 0)
    can = min(limit, M)

    vote += can

  if vote >= M * V:
    return True
  return False

while abs(ok - ng) > 1:
  mid = abs(ok + ng)//2
  if isOk(mid):

    ok = mid
  else:

    ng = mid
    
print(ok + 1)

Solution (Python):

from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = p
rv = n - v
rp = n - p
for i in range(rp):
    if a[i] + m < a[rp]:
        continue
    l = rp - i
    if (cs[rp + 1] - cs[i + 1]) + (l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

def cumsum(l):
    """a[i] = sum(l[:i]) なるaを返す
    """
    c = 0
    a = [None] * (len(l)+1)
    for i,num in enumerate(l):
        a[i] = c
        c += num
    a[-1] = c
    return a

s = cumsum(a)

def sub(i):
    
    if i>=n-p:
        return True
    if a[i] + m < a[-p]:
        return False
    v1 = a[i] + m
    ss = m * (i+p)
    tmps = (s[n-p+1] - s[i+1])
    ss += v1*(n-i-p) - tmps    
    r = ss >= m*v
    return r
l = 0
r = n-1
if sub(l):
    print(n)
else:
    while l<r-1:
        mm = (r+l)//2
        if sub(mm):
            r = mm
        else:
            l = mm
    print(n-1-l)

Solution (Python):
n, m, v, p = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mi = 0
ma = n - 1


def ok(i):
    if n - i <= p:
        return True
    if a[n - p] > a[i] + m:
        return False
    b = a[:]
    s = m * v - m
    b[i] += m
    for j in range(n - min(p-1, v-1), n):
        b[j] += m
        s -= m
    for j in range(n):
        if b[j] < b[i]:
            aa = min(b[i] - b[j], s, m)
            b[j] += aa
            s -= aa
    return s <= 0


while mi != ma:
    mm = (mi + ma) // 2
    if ok(mm):
        ma = mm
    else:
        mi = mm + 1
print(n - mi)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M,V,P = LI()
    A = LI()
    A.sort()

    ans = 0
    ac = list(itertools.accumulate(A))
    for i in range(N):
        if i >= N-P:
            ans += 1
            continue
        if M+A[i] < A[N-P]: continue
        if V <= P:
            ans += 1
            continue

        w = ((N-P-i) * (M+A[i])) - (ac[N-P] - ac[i])
        if w >= M * (V-P-i):
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=P
T=A[P-1]
for i in range(P,N):
 if A[P-1]-A[i]<=M and T-(i-P+1)*A[i]<=M*(N-V):
  ans+=1
 T+=A[i]
print(ans)

Solution (Python):
n,m,v,p= map(int, input().split())
a= list(map(int, input().split()))
a.sort(reverse=True)
ans=p
x = a[p - 1]
if v<=p:
    for i in range(p,n):
        if a[i]+m>=x:
            ans+=1
        else:
            break

else:
    
    b=[0]*n
    for i in range(p,n):
        b[i]+=b[i-1]
        b[i]+=x-a[i]

    for i in range(p,n):
        r=v-n+i-p+1
        if r<=0:
            if a[i]+m>=x:
                ans+=1
            else:
                break
        else:
            
            if r*m<=b[i-1]:
                x1=x
            else:
                x1=-(-(r*m-b[i-1])//(i-p+1))+x

            if a[i]+m>=x1:
                ans+=1
            else:
                break

print(ans)

Solution (Python):
N, M, V, P = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
total = [0]*N
total[0] = S[0]

for i in range(1, N):
    total[i] = total[i-1]+S[i]

if total[N-P]-total[0]+(V-P)*M <= (S[0]+M)*(N-P) and S[0]+M >= S[N-P]:
    ans = N
else:
    ok = N-1
    ng = 0
    while ng+1 < ok:
        mid = (ok+ng)//2
        if mid > N-P:
            ok = mid
        elif total[N-P]-total[mid]+(V-(P+mid))*M <= (S[mid]+M)*(N-P-mid) and S[mid]+M >= S[N-P]:
            ok = mid
        else:
            ng = mid
    ans = N-ok
print(ans)

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

if (v<=p):
    limit = a[n-p]
    if (a[n-p] <= m):
        print(n)
    else:
        x = bisect.bisect_left(a,a[n-p]-m)
        print(n-x)
else:
    limit = a[n-p]
    
    wa = [0]*n
    wa[0] = a[0]
    for i in range(1,n):
        wa[i] = wa[i-1] + a[i]
    
    ans = 0
    for i in range(n-p-1,-1,-1):
        sa = limit - a[i]
        if (sa==0):
            ans += 1
            continue
        elif (sa > m):
            continue
        if (i>=v):
            ans += 1
            
        else:
            nokori = (v-i-1-(p-1))*m
            
            
            if (nokori <= (a[i]+m)*(n-p-i) - (wa[n-p]-wa[i])):
                ans += 1
                
              
    print(ans + p)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m,v,p = map(int,readline().split())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)
ans = p
v -= (p-1)
g = a[p-1]
L = 1
use = m-g

for i in range(p,n):
  mar = g-a[i]
  V = v-(n-1-i)
  if mar > m:
    break
  if V <= 1:
    if mar <= m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break
  else:
    if use+a[i]*L >= (V-1)*m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break

print(ans)

Solution (Python):
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=p
border=a[p-1]
d=0
for i in range(p,n):
    
    if border>a[i]+m:
        break
    
    
    vote=m*(n-i)
    
    vote+=m*(p-1)
    
    vote+=d+(a[i]+m-border)*(i-p+1)
    
    if vote>=v*m:
        ans+=1
    d+=border-a[i]
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

rui=[0]
for i in range(p,n):
   rui.append(rui[i-p]+(a[p-1]-a[i]))


ans=p
tmp=0

for i in range(p,n):
    if a[p-1]<=a[i]+m:
        if n-i-1+p>=v:
            ans+=1
        else:
            mae=rui[i-p]+(a[i]+m-a[p-1])*(i-p+1)
            ushiro=(n-i-1)*m
            
            if mae+p*m+ushiro>=m*v:
                ans+=1

print(ans)

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
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i != mid:
      used += min(m, max(0, A[mid] + m - A[i]))
      if used >= m * v:
        break

  if used >= 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
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i != mid:
      used += min(m, max(0, A[mid] + m - A[i]))

  if used >= 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
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i == mid:
      continue

    used += min(m, max(0, A[mid] + m - A[i]))

  if used >= m * v:
    ok = mid
  else:
    ng = mid

print(ok + 1)

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

ls.sort()
total=m*v
for i in range(min(v-1,p-1)):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

l=-1
r=n
while l+1<r:
    i=(l+r)//2
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        l=i
        continue
    totalnow=total-m*(i+1)
    if totalnow <= 0:
        r=i
        continue
    ok=ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i)
    if ok< totalnow:
        l=i
        continue
    r=i

print(n-r)

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

ls.sort()
total=m*v
for i in range(min(v-1,p-1)):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

ans=p
for i in range(n-p):
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        continue
    totalnow=total-m*(i+1)
    if totalnow <= 0:
        ans += 1
        continue
    ok=ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i)
    if ok< totalnow:
        continue
    ans += 1

print(ans)

Solution (Python):
import bisect
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
eps = 0.1
def func(k):
    
    used = 0
    tmp = a[:k]+a[k+1:]
    val = a[k]+M
    x1 = N-1-bisect.bisect(tmp, val+eps)
    x2 = bisect.bisect(tmp, val-eps)
    x3 = N-(x1+x2+1)
    
    if x1 >= P:
        return False
    v = V - (x1+1)
    p = P - (x1+1)
    used += x1+1
    if v <= 0:
        return True
    
    
    if x3 >= p > 0:
        x3 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x3
        v -= x3
        used += x3
    if x2 >= p > 0:
        x2 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x2
        v -= x2
        used += x2
    if v <= 0:
        return True
    
    tmp2 = tmp[:N-used]
    rest = sum([min(M,val-val2) for val2 in tmp2])
    
    if rest >= M*v:
        return True
    return False

ok = N-1  
ng = -1  
while abs(ok - ng) > 1:
    cnt = (ok + ng) // 2
    t = func(cnt)
    
    if t:
        ok = cnt
    else:
        ng = cnt
print(N-ok)

Solution (Python):
import bisect
def main():

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

    prefix = [0]
    for i in range(N):
        prefix.append(prefix[-1] + A[i])

    ans = P
    for i in range(N-P):
        if A[i] + M >= A[N-P]:
            v = i * M + P * M
            v += (A[i] + M) * (N-P-i)
            v -= prefix[N-P+1] - prefix[i+1]
            if v >= M * V:
                ans += 1

    return ans

if __name__ == '__main__':
    print(main())

Solution (Python):
n, m, v, p = map(int, input().split())
a = [int(x) for x in input().split()]

a.sort(reverse=True)

l, r = 0, n
while r-l>1:
  key = (r+l)//2
  if key < p:
    l = key
    continue
  if a[key]+m < a[p-1]:
    r = key
    continue
  
  count = 0
  for i in range(n):
    if i < p-1 or i >= key:
      count += m
    else:
      count += a[key]+m-a[i]
  if count >= m*v:
    l = key
  else:
    r = key

print(r)

Solution (Python):
def check(n):

    if n <= P-1:
        return True

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-i for i in A[P-1:n]])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)


right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
def check(n):

    if n <= P-1:
        return True

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

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)


right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
def check(n):

    if n <= P-1:
        return True


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

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N
left = -1



"""
if check(right):
    print(N)
    exit()
"""
while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
def check(n):
    """
    if n <= P-1:
        return True
    """
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = P-1

if check(right):
    print(N)
    exit()

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
def check(n):

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

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
def check(n):

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

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1 and check(left) and not check(right):

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Solution (Python):
n,m,v,p=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort(reverse=True)

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    if a[x]+m<a[p-1]:
        return False
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=a[x]+m-a[i]
    if tmp>=m*v:
        return True
    return False

left=0
right=n
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Solution (Python):
n,m,v,p=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort(reverse=True)

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    if a[x]+m<a[p-1]:
        return False
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=min(m,a[x]+m-a[i])
    if tmp>=m*v:
        return True
    return False
left=-1
right=n
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Solution (Python):
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
broke = False
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            broke = True
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-P+1)
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    broke = True
                    break
    if broke == False:
        print(N)

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

a.sort()

l = -1
r = n-1
while r-l>1:
    i = (l+r)//2
    flag = 1
    if a[i]+m<a[n-p]:
        flag = 0
    elif i+p-1>=v:
        flag = 1
    else:
        rest = (v-i-p)*m
        for j in range(i+1,n-p+1):
            rest -= min(m,a[i]+m-a[j])
        if rest<=0:
            flag = 1
        else:
            flag = 0
    if flag:
        r = i
    else:
        l = i

print(n-r)

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

a = list(map(int, input().split()))
a.sort(reverse=True)

mv = m*max(0, v-p+1)
b = a[p-1:]

l, r = b[0], b[0]+m
while l < r:
    md = (l+r)//2
    c = 0
    for i in b:
        c += min(m, md-i)
    if mv <= c:
        r = md
    else:
        l = md + 1

result = p
for i in b[1:]:
    if i+m >= r:
        result += 1
    else:
        break
print(result)

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

a = list(map(int, input().split()))
a.sort(reverse=True)

mv = m*max(0, v-p+1)
b = a[p-1:]

l, r = b[0], b[0]+m
while l < r:
    md = (l+r)//2
    c = 0
    for i in b:
        c += min(m, md-i)
    if mv <= c:
        r = md
    else:
        l = md + 1

result = p
for i in b[1:]:
    if i+m >= r:
        result += 1
    else:
        break
print(result)

Solution (Python):
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
sa = [0 for _ in range(n+1)]
for i in range(n):
    sa[i+1] = sa[i] + a[i]

ans = p
for i in range(p, n):
    res = m * ((p - 1) + (n - i)) + \
          (a[i] + m) * (i - p + 1) - (sa[i] - sa[p-1])

    if res >= m * v and a[p-1] <= a[i] + m:
        ans += 1

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, V, P = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    A.sort()
    
    def check(t):
        if A[t] + M < A[-P]:
            return False
        at = A[t]
        cnt = (P - 1) * M
        for idx in range(N - P + 1):
            cnt += min(M, M - A[idx] + at)
        return M * V <= cnt
    
    ok, ng = N - 1, -1
    while 1 < ok - ng:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(N - ok)


if __name__ == '__main__':
    solve()

Solution (Python):
import copy

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

def condition(num):
    test=copy.copy(A)
    x=test[num]+M
    test[num]+=M
    test.sort(reverse=True)
    k=test.index(x)
    index=k+1
    if index>P:
        return False

    test=test[P:]
    yoyuu=0
    for i in range(0,len(test)):
        if x-test[i]>M:
            yoyuu+=M
        else:
            yoyuu+=x-test[i]

    return yoyuu>=M*(V-P)

A.sort()
start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if condition(t):
        end=t
    else:
        start=t

if condition(start):
    print(N-start)
else:
    print(N-end)

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


A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid -1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += A[mid]+M-v

        if voted >= M*V:
            left= mid+1
        else:
            right = mid-1

print(left)

Solution (Python):
def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    
    
    s=sum(a[p-1:p])
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        
        
        cnt+= ((a[i]+m)*(i-p+1)-s+(n-(i-p+1))*m)>=v*m
        try: s+=a[i]
        except: continue      
    print(cnt)

if __name__=='__main__':
    main()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def f(A, M, V, P, m):
    N = len(A)
    a = A[m]
    i = bisect.bisect_right(A, a + M)
    C = N - i

    if C >= P:
        return False

    C = P - 1
    i = N - C

    U = 0
    for j in range(i):
        if j == m:
            continue
        U += min(a + M - A[j], M)

    return U >= (V - 1 - C) * M


def main():
    N, M, V, P = read_values()
    A = read_list()
    A.sort()
    
    l = 0
    r = N
    while l < r:
        m = (r + l) // 2
        if f(A, M, V, P, m):
            r = m
        else:
            l = m + 1

    print(N - r)


if __name__ == "__main__":
    main()

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
        voted = (P-1)*M + (N-x)*M + M
        for i in range(P, x):
            voted += min(max((A[x-1] + M - A[i-1]), 0), M)
        if M*V <= voted:
            return True
        else:
            return False

    def binary_search_meguru():
        ng = N+1
        ok = P
        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):

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
        li = bisect.bisect_right(a,a[i])
        res = v-j-li
        if res <= 0:
            r = i
            continue
        res -= (p-j-1)
        s = 0
        for j in range(li,ri-(p-j-1)):
            s += A-a[j]
        if s >= res*m:
            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)


ok = P-1

ng = N

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

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

    used = 0
    
    used += M*P

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

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


print(ok+1)

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

A.sort()


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

l,r=-1,N-1
while r-l>1:
    m=(l+r)//2
    if check(m):
        r=m
    else:
        l=m
print(N-r)