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 bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split())) + [-M-1]
A.sort()

Ap = A[-P] 
I = N + 2 - P
right = N + 1 - P
left = 0

while left + 1 < right:
  mid = (left + right) // 2
  b = A[mid] + M
  if b < Ap:
    left = mid
  else:
    v = V - (bisect.bisect_right(A, A[mid])-1) - (P-1)
    if v <= 0:
      right = mid
    else:
      mv = M*v
      for i in range(mid+1, I):
        if A[i] == A[mid]:
          continue
        mv -= b - A[i]
        if mv <= 0:
          break
      if mv <= 0:
        right = mid
      else:
        left = mid

print(N + 1 - right)

Solution (Python):
import bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split())) + [-M-1]
A.sort()

Ap = A[-P] 
I = N + 2 - P
right = N + 1 - P
left = 0

while left + 1 < right:
  mid = (left + right) // 2
  b = A[mid] + M
  if b < Ap:
    left = mid
  else:
    v = V - (bisect.bisect_right(A, A[mid])-1) - (P-1)
    if v <= 0:
      right = mid
    else:
      mv = M*v
      for i in range(mid+1, I):
        if A[i] == A[mid]:
          continue
        mv -= b - A[i]
        if mv <= 0:
          break
      if mv <= 0:
        right = mid
      else:
        left = mid

print(N + 1 - right)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from collections import deque
import bisect

def main():
    N,M,V,P = map(int,input().split())
    a = sorted(list(map(int,input().split())),reverse=True)
    r = a[P-1]
    l = a[P-1]-M-1
    
    while r-l > 1:
        mid = (r+l)//2
        count = 0
        for x,num in enumerate(a):
            if x < P-1:
                count += M
            else:
                if num > mid:
                    count += max(mid+M-num,0)
                else:
                    count += M
        if count >= M*V:
            r = mid
        else:
            l = mid

    a.reverse()     
    print(N-bisect.bisect_left(a,r))
    
if __name__ == "__main__":
    main()

Solution (Python):
import bisect

n,m,v,p=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=0
for i in range(n):
  flag=False
  cnt=bisect.bisect_right(arr,arr[i])
  cnt2=bisect.bisect_right(arr,arr[i]+m)
  tv=v-cnt-min((p-1),n-cnt)
  rem=-1
  if cnt2<=n-p:
    ans+=0
  else:
    if tv<=0:
      ans+=1
      flag=True
    else:
      rem=acum[min(cnt2,n-(p-1))]-acum[cnt]
      if (arr[i]+m)*(min(cnt2,n-(p-1))-cnt)-rem>=m*tv:
        ans+=1
        flag=True
      else:
        ans+=0
print(ans)

Solution (Python):
N, M, V, P = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
m = A[P-1]
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  c = A[s]
  if m>c+M:
    r = s
    continue
  if s<P:
    l = s
    continue
  x = 0
  for i in range(N):
    if i<P-1:
      x += M
      continue
    if i>=s:
      x += M
      continue
    x += min(M,A[s]+M-A[i])
  if x>=M*V:
    l = s
  else:
    r = s
print(l+1)

Solution (Python):
from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
l = 0
r = n
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r-1:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid
    else:
        thresh = a[mid]+m 
        amari = (v-p)*m
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=min(m,thresh-a[i])
        if amari<=0:
            l = mid
        else:
            r=mid
print(l+1)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



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

A.sort(reverse=True)
cumA = [A[0]]
for i in range(1,N):
    cumA.append(cumA[-1]+A[i])

ans = P
if V < P:
    for i in range(P,N):
        if A[P-1] <= A[i]+M:
            ans += 1
else:
    for i in range(P,N):
        if A[i]+M < A[P-1]:
            continue
        cum = cumA[i-1]-cumA[P-2] if P >= 2 else cumA[i-1]
        cap = (i-P+1)*(M+A[i]) - cum + M*(N-i-1)
        if cap >= M*(V-P):
            ans += 1

print(ans)

Solution (Python):
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())))
if p >= v:
  print(sum([1 for b in a if b+m >= a[n-p]]))
else:
  s = p-1
  t = sum(a[:(n-p+1)])
  for i in range(n-p+1):
    t -= a[i]
    if a[i]+m >= a[n-p] and (a[i]+m)*(n-p-i) - t >= (v-p-i)*m:
      s += 1
  print(s)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict

con = 10 ** 9 + 7

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

def Binary_Search(A, N, M, V, P):
	
	
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M and A[mid] + M >= A[N - P]:
			ans = min(ans, mid)
			right = mid - 1
		elif mid >= N - P:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return N - ans


def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):

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

def is_ok(i):
    if i<0: return False
    cur,rival = A[i]+M, A[N-P]
    if cur < rival: return False
    rem_p = V - P - i
    if rem_p <= 0: return True
    j = 0
    for k in range(i+1,N-P+1):
        z = min(M, cur-A[k])
        j += z
        if j >= rem_p * M: return True
    return False

ok = N-P
ng = -1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(N-ok)

Solution (Python):
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
B=[0]
for i in range(n):
  B.append(B[-1]+A[i])

ok = -1
ng = n
if p>=1:
  while ng-ok > 1:
    mid = (ok+ng) // 2 
    
    if mid<p:
      ok=mid
      
    elif n-(mid+1)+p>=v:
      if A[p-1]<=A[mid]+m:
        ok=mid
        
      else:
        ng=mid
        
    else:
      if A[mid]+m>=A[p-1]:
        a=m*(v-n-p+mid+1)
        b=A[mid]+m
        q=p-1
        if (mid+1-p)*b-(B[mid]-B[q])>=a:
          ok=mid
          
        else:
          ng=mid
          
      else:
        ng=mid
        
  print(ok+1)

Solution (Python):

from bisect import *
from collections import *
from heapq import *



N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(i):

    B=[A[m] for m in range(N-(P-1)) if m!=i]

    C=A[i]+M
    a=V-P

    if C<A[-P]:
        return(0)
    else:
        if a>0:
            Votenum=a*M
            for b in B:
                Votenum-=min(C-b,M)
                if Votenum<=0:
                    return(1)

            return(0)
        else:
            return(1)




if main(0):
    print(N)
    exit()
st=0
end=N-P+1

while 1:
    a=(st+end)//2
    if main(a):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(st):
    print(N-st)
else:
    print(N-end)

Solution (Python):
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if A[t]+M<A[-P] or np.sum(np.minimum(M,A[t]+M-A[t+1:N-P+1]))<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

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

Solution (Python):
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    if indR<N-P+1:
        low = mid
        continue
    tot = M*V
    i = indL
    while i<N-P+1:
        if tot-(mid-A[i])<0:break
        tot -= mid-A[i]
        i += 1
    if i<N-P+1 or 0<=tot<=M*(P-1+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

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

def judge(x):
  if x >= n-p: return True
  if a[x] + m < a[n-p]: return False
  safe = m*(n-1) + a[x]*(n-p-x) - b[n-p+1] + b[x+1]
  return safe >= m*(v-1)

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,m,v,p = LI()
    a = sorted(LI())
    pi = n-p
    pv = a[pi]

    def f(i):
        t = a[i] + m
        if pv > t:
            return True
        mv = m*v-m
        for j in range(n):
            if j == i:
                continue
            aj = a[j]
            if j > pi:
                mv -= m
            elif aj <= t:
                mv -= min(m, t - aj)
            else:
                mv -= m
        return mv > 0

    r = bs(f,0,n-1)

    return n - r


print(main())

Solution (Python):
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor


"""

"""


def good(i):
    tv = A[i] + M
    max_used = (i + 1 + (P - 1)) * M
    free = M * V - max_used

    for j in range(i + 1, N - P + 1):
        if A[j] > tv:
            return 0
        free -= tv - A[j]

    return free <= 0


N = gi()
M = gi()
V = gi()
P = gi()
A = [0] * N
for i in range(N):
    A[i] = gi()
A.sort()



l = 0
h = N - 1

while l < h:
    mid = (l + h) // 2
    if good(mid):
        h = mid
    else:
        l = mid + 1

print(N - l)

Solution (Python):
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ap=a[p-1]
iok=p-1
ing=n
while ing-iok>1:
  x=(ing+iok)//2
  if x<=p-1:
    iok=x
  else:
    if a[x]+m<ap:
      ing=x
    else:
      if (p-1+n-x)*m+(x-(p-1))*(a[x]+m)-sum(a[p-1:x])>=m*v:
        iok=x
      else:
        ing=x
print(iok+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 ng-ok > 1:
    mid = (ok+ng)//2

    if v-1 <= p-2:
        if a[mid]+m >= a[p-1]:
            ok = mid
        else:
            ng = mid
    else:
        if a[mid]+m < a[p-1]:
            ng = mid
        else:
            r = v-p
            cnt = 0
            for i in range(p-1,n):
                if i == mid:
                    continue
                cnt += min(m,a[mid]+m-a[i])
            if cnt >= r*m:
                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()
A = A[::-1]


left = 0
right = N

while left + 1 < right:
  mid = (left + right) // 2
  Amid = A[mid]
  rest = M * V - M * P
  start = P if mid + 1 <= P else P - 1
  
  flag = 0
  for i in range(start, N):
    if mid == i:
      continue
    else:
      if A[i] > Amid + M:
        flag = 1
        break
      else:
        rest -= min(M, Amid + M - A[i])
        
  if rest > 0 or flag:
    right = mid
  else:
    left = mid


answer = 0
Aleft = A[left]
for i in range(N):
  if A[i] >= Aleft:
    answer += 1
    
print(answer)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)

    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,v,p = inpm()
    a = inpl()
    a.sort(reverse=True)
    ok = 0
    ng = n
    while ng-ok >1:
        mid = (ok+ng)//2
        if mid+1 <= p:
            ok = mid
        elif a[p-1] > a[mid]+m:
            ng = mid
        else:
            key = 0
            cnt = (p)*m + (n-mid-1)*m
            for i in range(mid-1,p-2,-1):
                if a[i] > a[mid]+m:
                    ng = mid
                    key = 1
                    break
                cnt += min(a[mid]-a[i]+m,m)
            if key:
                break
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate

N, M, V, P, *A = map(int, open(0).read().split())

A.sort(reverse=True)

S = list(accumulate(A)) + [0]

def is_ok(md):
    return (A[md] + M < A[P - 1]) or (A[md] + M) * (md - P + 1) - (S[md - 1] - S[P - 2]) < M * (V - (P - 1) - (N - md))

ng, ok = P - 1, N
while ok - ng > 1:
    md = (ok + ng) // 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

Solution (Python):

import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)
    L = M*(V-N)-acc[P-1]
    K = A[P-1]-M
    while right - left > 1:
        mid = (right + left)//2
        cap = (mid-P+1)*A[mid] - acc[mid]
        if A[mid] < K or cap < L:
            right = mid
        else:
            left = mid
    print(right)

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

import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)
    L = M*(V-N)-acc[P-1]
    K = A[P-1]-M
    while right - left > 1:
        mid = (right + left)//2
        cap = (mid-P+1)*A[mid] - acc[mid]
        if A[mid] < K or cap < L:
            right = mid
        else:
            left = mid
    print(right)

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

import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    ans = 0

    
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

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

        cap = M*N+(mid-P+1)*(A[mid]) - acc[mid] + acc[P-1]
        if cap >= M*V:
            left = mid
        else:
            right = mid
    print(left+1)

    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):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
    for i in range(p-1,n):
        if i==k:
            continue
        tot-=min(max(0,mx-b[i]),m)

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

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

ok=b[l]
ans=sum([1 if i>=ok else 0 for i in b])
print(ans)

Solution (Python):
import numpy as np

N,M,V,P = map(int,input().split())
A = np.sort(list(map(int,input().split())))[::-1]

Ap = A[P-1]
iOK = P-1
iNG = N
while iOK+1 < iNG:
    x = (iOK+iNG)//2
    if x <= P-1:
        iOK = x
    elif Ap - A[x] > M:
        iNG = x
    elif (P-1)+(N-x) >= V:
        iOK = x
    elif (A[x]+M)*(x-P+1)-np.sum(A[P-1:x]) >= M*(V-P+1-N+x):
        iOK = x
    else:
        iNG = x

ans = iOK + 1
print(ans)

Solution (Python):

import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    ans = 0

    
    A.sort(reverse=True)

    acc = [0]+list(accumulate(A))

    for i in range(N):
        
        if i < P:
            ans += 1
            continue
        
        if A[i]+M < A[P-1]:
            continue

        
        
        cap = 0
        
        cap += M*(P-1)
        
        cap += M*(N-i)
        
        
        
        cap += (i-P+1)*(A[i]+M)
        
        
        cap -= acc[i] - acc[P-1]
        if cap >= M*V:
            ans += 1
    print(ans)

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


import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

def check(m):
    
    if m >= N - P:
        return True
    
    target = A[m] + M
    
    total = M * (V-1)
    
    r = bisect_right(A, target)
    if r <= N - P:
        return False
    
    total -= M * m
    
    total -= M * (P-1)
    
    for i in range(m+1, N-P+1):
        total -= target - A[i]
    
    return total <= 0

N, M, V, P = MAP()
A = LIST()

A.sort()
res = bisearch_min(-1, N-1, check)
ans = N - res
print(ans)

Solution (Python):
n,m,v,p,*a=map(int,open(0).read().split())
A=sorted(a)[-p::-1]
s=m*v-m*n
u=0
for a in A:
 if(A[0]-m)*u<=a*u>=s:s+=a;u+=1
print(p-1+u)

Solution (Python):
n,m,v,p,*a=map(int,open(0).read().split())
a=sorted(a)[::-1]
ok=p-1
ng=n
while ng-ok>1:
  mid=(ok+ng)//2
  c=a[mid]+m
  s=f=0
  for t in a[p-1:mid]:
    if t>c:break
    s+=c-t
  else:f|=(p-1+n-mid)*m+s>=v*m
  if f:ok=mid
  else:ng=mid
print(ok+1)

Solution (Python):
n,m,v,p,*a=map(int,open(0).read().split())
a=sorted(a)[::-1]
ok=p-1
ng=n
while ng-ok>1:
  mid=(ok+ng)//2
  c=a[mid]+m
  s=f=0
  for t in a[p-1:mid]:
    if t>c:break
    s+=c-t
  else:f|=(p-1+n-mid)*m+s>=v*m
  if f:ok=mid
  else:ng=mid
print(ok+1)

Solution (Python):
def nibutan(L):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if nasu(mid, L):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n, L):
  p = L[n] + M
  if p < L[K]:
    return False
  m = (V - 1 - (n + P - 1)) * M
  if m <= 0:
    return True
  for i in range(n + 1, K + 1):
    m -= p - L[i]
    if m <= 0:
      return True
  return False

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

A.sort()
K = N - P
T = A[K]
print(N - nibutan(A))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
x = a[p-1]
a = a[p-1:]
l = list(accumulate(a))
ans = p

for i in range(n-p):
    if a[i+1] + m < x:
        continue
    s = (n-(p+i+1))*m + p*m
    s += (a[i+1] + m) * (i+1)
    s -= l[i]
    if s >= m*v:
        ans += 1
print(ans)

Solution (Python):



def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = -1, n

    while left+1 < right:
        i = (left+right)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import sys
import math
import numpy as np

stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m, v, p = na()
a = na()
a.sort(reverse=True)
a = np.array(a)
left = p - 1
right = n
def check(i):
    c = a[i] + m
    s = (p-1) * m + np.sum(np.minimum(c - a[p-1:], m))
    if i+1 <= p:
        return True
    elif a[i] + m < a[p-1]:
        return False
    elif s >= m * v:
        return True
    else:
        return False
while left + 1 < right:
    x = (left + right) // 2
    if check(x):
        left = x
    else:
        right = x
print(left + 1)

Solution (Python):
import sys
import math
import numpy as np

stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m, v, p = na()
a = na()
a.sort(reverse=True)
a = np.array(a)
left = 0
right = n
def check(i):
    c = a[i] + m
    s = (p-1) * m + np.sum(np.minimum(c - a[p-1:], m))
    if i+1 <= p:
        return True
    elif a[i] + m < a[p-1]:
        return False
    elif s >= m * v:
        return True
    else:
        return False
while left + 1 < right:
    x = (left + right) // 2
    if check(x):
        left = x
    else:
        right = x
print(left + 1)

Solution (Python):
import sys
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ng = -1
ok = N - P

def check(x):
  vs = M * V
  p = N
  for i in range(N):
    if a[i] > a[x] + M:
      p = i - 1
      break
  
  if p < N - P: return False
  
  for i in range(N - P + 1, N):
    vs -= M
  
  for i in range(N - P + 1):
    vs -= min(max(a[x] + M - a[i], 0), M)

  
  return vs <= 0

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

Solution (Python):
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

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

S = cumulative_sum(A)

def check(i):
    s = max(0,S.get(i+1,N-P+1))
    res = max(M*(V-P-i),0)
    if A[i]+M<A[N-P]: return False
    return ((A[i]+M)*max(0,N-P-i))>=s+res

ans = sum(check(i) for i in range(N))
print(ans)

Solution (Python):
n,m,v,p=map(int,input().split())
A=sorted(list(map(int,input().split())))[-p::-1]
s=m*v-m*n;u=0
for a in A:
 if a<A[0]-m or s>u*a:break
 s+=a;u+=1
print(p-1+u)

Solution (Python):
n,m,v,p=map(int,input().split())
A=sorted(list(map(int,input().split())))[-p::-1]
s=0;p-=1
for u,a in enumerate(A):
 if a<A[0]-m or u*a+m*n-m*v<s:break
 s+=a;p+=1
print(p)

Solution (Python):
n,m,v,p=map(int,input().split())
p-=1
A=sorted(list(map(int,input().split())),reverse=True)[p:]
s=0
for u,a in enumerate(A):
 if a>=A[0]-m and u*a+m*n-m*v>=s:s+=a;p+=1
 else:break
print(p)

Solution (Python):

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


def isOK(i):  
    
    need = M * (P-1)
    
    need += M
    
    
    need += M * (N-i-1)
    ai = A[i]+M  
    s = 0
    for j in range(P-1, i):
        d = ai - A[j]
        if d < 0:
            return False
        s += d
    
    if need + s >= M*V:
        return True
    else:
        return False


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  
        left = mid
    else:  
        right = mid

print(left + 1)

Solution (Python):

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

capacity = M * (N-V)


def isOK(i):
    ai = A[i]  
    s = 0
    
    
    for j in range(P-1, i):
        d = A[j] - ai
        
        if d > M:  
            return False
        s += d
    if s > capacity:
        return False
    else:
        return True


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  
        left = mid
    else:  
        right = mid
print(left + 1)