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):
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    if x > n - p:
        return True

    for i in range(x + 1, n - p + 1):
        if a[x] + m < a[i]:
            return False

    if v - x - p > 0:
        cnt = 0
        for i in range(x + 1, n - p + 1):
            cnt += min((a[x] + m) - a[i], m)

        if (cnt // (v - x - p)) >= m:
            return True
        else:
            return False
    else:
        return True


lb = -1  
ub = n - 1  
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid



ans = n - ub
print(ans)

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

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-1:]
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return True

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    print(n-b_search(0, n-1, value))


main()

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

def ok(x):
    if x + M < A[P-1]:
        return False
    sc = M * V
    for a in A[:P-1]:
        sc = sc - M
    for a in A[P-1:]:
        sc = sc - min(M, x + M - a)
    return sc <= 0

l, r = -1, N
while r - l > 1:
    m = l + (r - l) // 2
    if not ok(A[m]):
        r = m
    else:
        l = m
print(r)

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

a = sorted(a)

sm = sum(a[:n-p+1])

for k in range(n-p+1):
    sm -= a[k]
    if a[k]+m < a[n-p]:
        continue
    elif (n-p-k)*(a[k]+m) - sm +(p+k)*m < v*m:
        continue
    else:
        print(n-k)
        exit()

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

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-1:]
        
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return True
        

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    

    print(n-b_search(0, n-1, value))


main()

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

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

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


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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def check(x,N,M,V,P,A):
    if (N-x)<=P:
        return True
    if(V<=x+P):
        return(A[x]+M>=A[N-P])

    x_score = A[x]+M
    total_v = (V-x-P)*M

    if(A[N-P]>x_score):
        return False

    for i in range(x+1,N-P+1):
        total_v -= min(M,(x_score - A[i]))
    if total_v <= 0:
        return True
    else:
        return False

def main():
    N,M,V,P = map(int,input().split())
    A = [int(x) for x in input().split()]
    A.sort()

    if(check(0,N,M,V,P,A)):
        print(N)
        return

    isOK = N-1
    isNG = 0
    while(isOK-isNG>1):
        middle = (isOK+isNG)//2
        if(check(middle,N,M,V,P,A)):
            isOK = middle
        else:
            isNG = middle
    print(N-isOK)
    return


if __name__ == "__main__":
    main()

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-1):
        return True

    points = a.copy()

    points[i] += m

    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        return False

    j = n-1
    while adding_point > 0:

        if j <= p-2:
            return False

        if i == j:
            j -= 1
            continue
        adding_point -= min(m, points[i]- points[j])

        j -= 1

    return True

if isok(n-1):
    print(n)
    exit()

ok = p-1
ng = n-1

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

    if isok(mid):
        ok = mid
    else:
        ng = mid
print(ok+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()

OK=N-P
NG=-1

while OK-NG>1:
    
    mid=(OK+NG)//2
    

    if (P-1)+mid+1>=V:
        if A[-P]<=A[mid]+M:
            OK=mid
        else:
            NG=mid

    else:
        V2=V-(P-1)-mid
        A2=A[mid:N-P+1]

        

        BASE=A2[0]+M
        k=0

        if BASE<A2[-1]:
            NG=mid
            continue
            
        for a in A2[1:]:
            k+=(BASE-a)

        

        if k<M*(V2-1):
            NG=mid
        else:
            OK=mid


print(N-NG-1)

Solution (Python):
def examA():
    N, A, B = LI()
    ans = inf
    if abs(A-B)%2==0:
        ans = abs(A-B)//2
    cur = min((A+B-1)//2,(2*N-A-B+1)//2)
    ans = min(ans,cur)
    print(ans)
    return

def examB():
    N, M, V, P = LI()
    A = LI(); A.sort()
    maxA = A[N-P]
    sumA = maxA*(N-P)-sum(A[:N-P])

    l = -1; r = N-P
    while(r-l>1):
        flag = True
        now = (l+r)//2
        c = sumA - (maxA-A[now])
        need = maxA - A[now]
        if need>M:
            flag = False
        q = 0
        for i in range(N):
            if A[i]>=maxA-M+(M-need):
                break
            if i==now:
                break
            q +=maxA-M+(M-need)-A[i]
        if (V-P)*M-(N-P)*(M-need)+q>c:
            flag = False
        if flag:
            r = now
        else:
            l = now

    ans = N-r
    print(ans)
    return

def examC():
    N = I()
    ans = [["."]*N for _ in range(N)]
    if N%3!=0 and N%2!=0:
        print("-1")
        return
    if N%3==0:
        for i in range(N//3):
            ans[i*3][i*3] = "a"
            ans[i*3][i*3+1] = "a"
        for i in range(N//3):
            ans[i*3+1][i*3+2] = "a"
            ans[i*3+2][i*3+2] = "a"
    else:
        for i in range(N//2):
            for j in range((N+2) // 4):
                ans[i * 2][j * 4] = "a"
                ans[i * 2][j * 4 + 1] = "a"
                ans[i * 2 + 1][j * 4] = "b"
                ans[i * 2 + 1][j * 4 + 1] = "b"
                if j*4+2==N:
                    break
                ans[i * 2][j * 4+2] = "c"
                ans[i * 2][j * 4+3] = "c"
                ans[i * 2 + 1][j * 4 + 2] = "d"
                ans[i * 2 + 1][j * 4 + 3] = "d"
            ans[i*2][i*2] = "e"
            ans[i*2+1][i*2] = "e"
            ans[i*2][i*2+1] = "f"
            ans[i*2+1][i*2+1] = "f"
    for v in ans:
        print("".join(map(str,v)))
    return

def examD():
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()


"""
                for j in range(N // 4):
                    ans[i * 2][j * 4+2] = "a"
                    ans[i * 2][j * 4 +3] = "a"
                    ans[i * 2 +1][j * 4+2] = "b"
                    ans[i * 2 +1][j * 4 +3] = "b"
                for j in range(N // 4):
                    ans[i*2-2][j*4+2] = "c"
                    ans[i*2-1][j*4+2] = "c"
                    ans[i*2-2][j*4 +3] = "d"
                    ans[i*2-1][j*4 +3] = "d"

"""

Solution (Python):
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
ans = p
c = [0]
cnt = 0
for i in range(n):
  
  cnt += a[i]
  c.append(cnt)
  
from bisect import bisect_right
for i in range(p,n):
  h = a[i]+m
  free = v - (p-1) - (n-i)
  if free >= 0 and h >= a[p-1]:
    d = h * (i-p+1) - (c[i]-c[p-1]) 
    if d >= free*m:
      ans += 1
  else:
    if h >= a[p-1]:
      ans += 1
print(ans)

Solution (Python):
import numpy as np
i8 = np.int64

f = open('/dev/stdin', 'rb')
pin = np.fromstring(f.read(), i8, sep=' ')
N, M, V, P = pin[: 4]
a = pin[4:4 + N]

x = np.arange(N - P)
N -= P - 1
V -= P - 1
a = np.sort(a)[::-1][P - 1:]
top = a[0]
cumsum = np.cumsum(a)[: -1]
a = a[1:]

filter = np.logical_and(a + M >= top, (a + M) * (x + 1) - cumsum - (x + 1 - (N - V))*M >= 0)
print(np.count_nonzero(filter) + P)

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

A.sort()
sumtab = [0] * (N + 1)
tmp_tab = 0
for i, Ai in enumerate(A):
    tmp_tab += Ai
    sumtab[i + 1] = tmp_tab

l = 0
r = N
while True:
    i = l + (r - l) // 2
    
    
    B = list(A)
    
    score_i = A[i] + M
    B[i] += M
    M_tmp = M * (V - 1)
    
    rslt = False
    
    for j in list(range(N))[::-1]:
        
        if j == i:
            continue 
        elif j > N - P:
            
            tmp = min(M, M_tmp)
            
            M_tmp -= tmp
            B[j] += tmp
        else:
            
            if A[j] > score_i:
                break
            if A[j] + M <= score_i:
                tmp = min(M, M_tmp)
            else:
                tmp = min(score_i - A[j], M_tmp)
            
            M_tmp -= tmp
            B[j] += tmp
        
        if M_tmp <= 0: break
    
    
    if i >= N - P:
        r = i
    elif M_tmp <= 0 and score_i >= B[N - P]:
        r = i
    else:
        l = i + 1
    
    if l >= r: break
        
print(N - l)

Solution (Python):

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

A_list.sort(reverse = True)

ans = P
border = A_list[P - 1]
sum_over_A = border

if P < N:
    before_A = border
    for i in range(P, N):
        if before_A == A_list[i]:
            ans += 1

        elif border <= (A_list[i] + M):
            over_V = V - (P + N - (i + 1))
            if over_V > 0:
                sum_over = sum_over_A + over_V * M
                round_up_sum_over = -(-sum_over // (i + 1 - P))
                if A_list[i] + M >= round_up_sum_over:
                    ans += 1

                else:

                    break
            else:
                ans += 1

            before_A = A_list[i]
        else:
            break
        sum_over_A += A_list[i]
print(ans)

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

A.sort()
Cumsum=list(itertools.accumulate(A))
Kijun=A[n-p]
Ans=n
for i in range(n):
   L=0
   if A[i]+m>=Kijun:
       b1=min(bisect.bisect_left(A, A[i]+m),n-p)
       b2=min(bisect.bisect_right(A, A[i]+m),n-p) 
       L=m*(i+1)+(A[i]+m)*(b1-i)-(Cumsum[b1]-Cumsum[i])+m*(n-b2-1)
       if L>=m*v:
            break

print(n-i)

Solution (Python):
from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n,m,v,p = mi()
    atmp = li()
    
    atmp = list(sorted(atmp))
    a = []
    ad = []

    for i in range(n):
        a.append([atmp[i],i])
        ad.append([atmp[i],i])


    
    

    a = list(sorted(a, key=lambda x : x[0]))
    


    l = 0
    r = n-1
    mid = (r-l)//2+l

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

        if mid >= n-p:
            r = mid
            continue

        tmpmax = a[mid][0]+m
        tmp = m*(v-1)

        if tmpmax < a[n-p][0]:
            l = mid
            continue

        

        flag = False
        for itmp in range(n):
            i =n-1-itmp
            if i == mid:
                continue
            if itmp <= p-2:
                tmp-=m
            else:
                if a[i][0] > tmpmax:
                    l = mid
                    flag = True
                    break
                tmp-=(min(tmpmax-a[i][0],m))
                
        if flag:
            continue
        else:
            
            if tmp >0:
                l = mid
            else:
                r = mid
    
    if r == 1:
        mid = 0
        tmpmax = a[mid][0]+m
        tmp = m*(v-1)

        if tmpmax < a[n-p][0]:
            l = mid

        

        flag = False
        for itmp in range(n):
            i =n-1-itmp
            if i == mid:
                continue
            if itmp <= p-2:
                tmp-=m
            else:
                if a[i][0] > tmpmax:
                    l = mid
                    flag = True
                    break
                tmp-=(min(tmpmax-a[i][0],m))
                
        else:
            
            if tmp >0:
                l = mid
            else:
                r = mid




    print(n-r)



    
main()

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

B = [0] * n
B[p - 1] = A[p - 1]

count = 0
for i in range(p - 1, n - 1):
    if A[i] == A[i-1]:
        count += 1
        B[i + 1] = B[i]
    else:
        B[i + 1] = B[i] + A[i + 1] + count * A[i]
        count = 0

if v <= p:
    for i in range(p, n):
        if target - A[i] <= m:
            ans += 1
    print(ans)
    exit()
else:
    ans -= 1
    lim = m * (n - v)
    for i in range(p - 1, n):
        if i == 0:
            ans += 1
        else:
            temp = B[i - 1] - (i - p + 1) * A[i]
            if A[i] == A[i - 1] or (temp <= lim and target - A[i] <= m):
                ans += 1
            else:
                print(ans)
                exit()
    print(ans)
    exit()

Solution (Python):

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

for i in range(1,N):
    A_wa.append(A_wa[i-1]+A[i])
A_wa.append(0)
def bin_isOK(index):
    if A[index]+M < A[N-P]:
        return False
    
    
    
    if (A[index]+M)*(N-P-index+1) - (A_wa[N-P] - A_wa[index-1]) >= V*M-M*(P-1+index):
        return True
    else:
        return False


def binary_search():
    ng = -1
    ok = N-P

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

        if bin_isOK(mid):
            ok = mid
        else:
            ng = mid
    
    return ok





print(N-binary_search())

Solution (Python):
n,m,v,p=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
a=a[p-1:]
le=len(a)
l,r=0,le-1

def adopt(x):
    global a,n,m,v,p
    b=a[x]+m
    if b<a[0]:
        return False
    al=v*m
    al-=(n-x)*m
    if al<=0:
        return True
    s=x*b-sum(a[:x])
    
    
    if al>s:
        return False
    else:
        return True

while l+1<r:
    
    
    k=(l+r)//2
    if adopt(k):
        l=k
    else:
        r=k

if adopt(r):
    print(p+r)
else:
    print(p+l)

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

A.sort()
B = [0]*N
B[0] = A[0]

for i in range(1,N):
    B[i] = B[i-1] + A[i]



mn = 0 
mx = N-1 
while True:
    k = (mn+mx)//2
    
    c = A[k]
    c += M
    p = bisect.bisect_right(A,c)
    flag = False
    
    
    
    ALL = V*M
    ALL -= (k+1)*M 
    ALL -= (P-1)*M 
    if N-P < p:
        if ALL <= 0:
            flag = True
        
        
        res = c*(N-P-k) - (B[N-P] - B[k])
        
        if ALL <= res:
            flag = True
    
    if mx - mn == 1:
        if flag:
            mx = k
        else:
            mn = k
        break
    if flag:
        mx = k
    else:
        mn = k

print(N-mx)

Solution (Python):
input = raw_input


def answer():
    n, m, v, p = map(int, input().split(" "))
    nums = sorted(map(int, input().split(" ")), reverse=True)

    num_last = nums[p-1]

    nokori_sum = sum(nums[p-1:n])

    out = p
    count = 0
    if v > p:
        cumsum = {}
        cur = 0
        
        cur = 0
        for i in range(p-1, n):
            x = nums[i]
            cur += x
            cumsum[i] = cur

        for i in range(p, n):
            x = nums[i]
            if x + m < num_last:
                break

            
            
            
            
            
            
            
            

            area1 = (x+m) * (i-p+1) - cumsum[i-1]
            
            area2 = (n - i - 1) * m
            

            nokori_yoyuu = area1 + area2

            cost = (v-p) * m
            if cost > nokori_yoyuu:
                break

            count += 1

        out += count

    else:
        for x in nums[p:]:
            if x + m < num_last:
                break
            count += 1
        out += count

    print(out)

answer()

Solution (Python):
import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n, m, v, p = [int(x) for x in input().strip().split()]
araw = sorted([int(x) for x in input().strip().split()])
a = list(reversed(araw))

def f(x, n, m, v, p, a, araw):
    c = p - (n - bisect_right(araw, a[x-1]+m)) - 1
    if c < 0:
        return False
    vote = m * (v - 1)
    a[x-1] += m
    thr = a[x-1]
    for i, aa in enumerate(a, start=1):
        if vote <= 0:
            break
        if i == x:
            continue
        if aa > thr:
            a[i-1] += m
            vote -= m
        elif aa == thr:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
        elif thr - aa < m:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
            else:
                v_ = min(vote, thr - aa, m)
                a[i-1] += v_
                vote -= v_
        else:
            a[i-1] += m
            vote -= m
    return vote <= 0

x = 0
l = 1
r = n + 1
while l < r:
    x = (l + r) // 2
    if f(x, n, m, v, p, a[:], araw):
        l = x + 1
    else:
        r = x
print(l-1)

Solution (Python):

import sys


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

    A.sort(reverse=True)

    I = N

    for i in range(P, N):
        if A[P-1] > A[i] + M:
            I = i
            break

    l = P-1
    r = I
    m = (l + r)//2

    while l + 1 != r:

        k = (V-P)*M - M*(N-I)
        for i in range(P-1, I):
            if i == m:
                continue
            k -= min(A[m] + M -A[i], M)
            if k <= 0:
                l = m
                m = (l+r)//2
                break
        if k > 0:
            r = m
            m = (l+r)//2

    print(l+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):
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)


ans = [0] * n
for i in range(p):
    ans[i] = 1

index = p 
for i in range(p, n):
    if a[i] == a[p-1]:
        ans[i] = 1
        index += 1
    else:
        break

if index == n:
    print(sum(ans))
    exit()



mn = a[p-1]





if v - p <= 0:
    for i in range(p, n):
        if a[i] + m >= mn:
            ans[i] = 1
        else:
            break
    print(sum(ans))
    exit()






large = [0] * n
small = [0] * n
for i in range(p, n):
    if i == p:
        large[p] = 0
        small[p] = n - 1 - p
    else:
        if a[i] == a[i-1]:
            large[i] = large[i-1]
            small[i] = small[i-1]
        else:
            large[i] = i - p
            small[i] = n - 1 - i


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

for i in range(p, n):
    unvote = v - p - small[i]
    if unvote <= 0:
        if a[i] + m >= mn:
            ans[i] = 1
    else:
        if a[i] + m < mn:
            break
        
        sm = acum[p + large[i]] - acum[p-1]
        if sm + unvote * m <= (a[i] + m) * (large[i]+1):
            ans[i] = 1

print(sum(ans))

Solution (Python):
n, m, v, p = [int(_) for _ in input().split()]
l = [int(_) for _ in input().split()]

l = sorted(l, reverse=True)



s = [0]


for i in range(1, n+1):
    s.append(s[-1] + l[-i])
s = sorted(s, reverse=True)



for i in range(p, n):
    if l[i] + m < l[p - 1]:
        ans = i
        break
    x = (l[i] + m) * (i - p + 1) - (s[p - 1] - s[i])
    
    
    
    
    
    y = 0
    if v >= (n - i) + (p - 1):
        y = v - (n - i) - (p - 1)

    

    if x < y * m:
        ans = i
        break

    if i == n-1:
        ans = n

print(ans)

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

def binary_search(S,k,m,v,p):
  test=S[k]+m
  cnt=m*(p-1)
  l=0
  for i in range(p-1,n):
    if i==k:
      continue
    elif test<S[i]:
      l=1
      return False
      break
    elif test-S[i]>=m:
      cnt+=m
    else:
      cnt+=test-S[i]
      
  if l==0:
    if cnt>=m*(v-1):
      return True
    else:
      return False

l=p-1
r=n
while r-l>1:
  mid=(r+l)//2
  if binary_search(S,mid,m,v,p):
    l=mid
  else:
    r=mid
print(l+1)

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

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []

A.sort()
for _ in range(P-1):
    B.append(A.pop())

try:
    C.append(A.pop())
    while C[-1] == A[-1]:
        C.append(A.pop())
except:
    pass

A_length = len(A)
B_length = len(B)
C_length = len(C)
sm = sum(C)
count = 0

for _ in range(len(A)):
    now = A[-1]
    new = now + M
    threshhold = C
    remain = V - B_length - (A_length - count)
    if new >= C[0]:
        if remain <= 0:
            val = A.pop()
            C.append(val)
            sm += val
            count += 1
        elif sm <= new * (C_length + count) - remain*M:
            val = A.pop()
            C.append(val)
            sm += val
            count += 1
print(len(B+C))

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

AP = A[P-1]
D = [AP - A[i] for i in range(N)]
if V <= P:
	for i in range(N):
		if D[i] > M:
			print(i)
			exit()
l,r = P-1,N
while r - l > 1:
	p = (l+r)//2
	
	if D[p] > M:
		r = p
		continue
	n = P + (N-1 - p)
	if V <= n:
		l = p
		continue
	v = V - n
	d = []
	m = A[p] + M
	sumd = []
	nonzero = p
	for i in range(P-1, p):
		diff = min(M, m - A[i])
		if nonzero == p and diff > 0:
			nonzero = i
		d.append(diff)
		if i == P-1:
			sumd.append(diff)
		else:
			sumd.append(sumd[-1] + diff)
	if sumd[-1] < v * M or p - nonzero < v:
		r = p
	else:
		l = p

print(r)

Solution (Python):
from collections import Counter


def solve(n, m, v, p, aaa):
    aaa.sort(reverse=True)
    count = Counter(aaa)
    scores = sorted(count.keys(), reverse=True)

    tmp_cnt = 0
    for pi, s in enumerate(scores):
        c = count[s]
        tmp_cnt += c
        if tmp_cnt >= p:
            ans = tmp_cnt
            rival = s
            htm_cnt = tmp_cnt - (p - 1)  
            htm_sum = s * htm_cnt
            break
    else:
        raise RuntimeError

    
    
    

    for s in scores[pi + 1:]:
        c = count[s]
        upper = s + m
        if upper < rival:
            break

        v4mtm = v - (n - htm_cnt)  
        if v4mtm <= 0:
            ans += c
        else:
            space = upper * htm_cnt - htm_sum
            if space >= m * v4mtm:
                ans += c

        htm_cnt += c
        htm_sum += s * c

    return ans


n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))

Solution (Python):
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = A[:N-P+1]
S = sum(B)
accum = [0]
for i in range(N-P+1):
    accum.append(accum[-1]+B[i])

ans = P-1

for i in range(N-P+1):
    if B[i]+M-B[-1]<0:
        continue
    if B[i]*(N-P-i)-S+accum[i+1]+M*(N-P)>=max(M*(V-P),0):
        ans += 1

print(ans)

Solution (Python):
import math
N, M, V, P = map(int, input().split())
A_ = list(map(int, input().split()))
A = sorted(A_)
temp = 0
requires = 0
for i in range(N-P):
  requires += A[N-P] - A[i]
for i in range(N):
  points = V - P - i
  if points < 0:
    points = 0
  requires -= A[N-P] - A[i]
  kabe = N - P - i
  if kabe == 0:
    temp = i
    break
  else:
    wall = points * M - requires
    if wall < 0:
      wall = 0
    wall_2 = math.ceil(wall / kabe)
    wall_3 = A[N-P] + wall_2
    i_points = A[i] + M
    if i_points >= wall_3:
      temp = i
      break
print(N - temp)

Solution (Python):





import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 

n,m,v,p = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]


def number(res,w):
    ans = 0
    for i in res:
        ans += min(m,i)
    
    
    if ans < w*m: return False
    else: return True
    



def check(c):
    M = a[c]+m
    if a[n-p] > M: return False

    w = v-c-1-(p-1)
    if w <= 0: return True
    
    res = []
    for i in range(c+1, n-p+1):
        res.append(M-a[i])
    
    
    
    return number(res,w)


a.sort()

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


print(n-ng-1)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, M, V, P = inpl()
A = inpl()
A.sort(reverse=True)
s = 0
S = []
for i in range(N):
    s += A[i]
    S.append(s)
S.append(0)
OK = P-1
NG = N
while NG - OK > 1:
    x = (NG+OK)//2
    if A[P-1] > A[x] + M:
        NG = x
    elif P + (N-1-x) >= V:
        OK = x
    else:
        remain = M * (V-P-(N-1-x))
        space = (x-P+1)*(A[x]+M) - (S[x-1] - S[P-2])
        if remain <= space:
            OK = x
        else:
            NG = x
print(OK+1)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

B=A[:]
A.append(inf)
for i in range(n-1):
    B[i+1]+=B[i]
i=0
while i < n:
    count=1
    while A[i]==A[i+1]:
        i+=1; count+=1
    K=v-p-(i)
    
    if i>=n-p:
        ans+=count; i+=1
        continue
    if K<=0:
        if bisect.bisect_right(A,A[i]+m)>=n-p+1:
            ans += count
            i+=1
        else:
            i+=1
    else:
        if A[n-p]>A[i]+m:
            i+=1
        else:
            S=B[n-p]-B[i]
            if (A[i]+m)*(n-p-i)>=S+K*m:
                ans+=count
                i+=1
            else: i+=1
print(ans)

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







def vote(x):
    if x >= n - p:
        return True
    elif x == -1:
        return False
    else:
        total_vote = m * (v-1)
        b_list = a_list[::]
        b_list[x] += m

        if b_list[x] < b_list[n-p]:
            return False

        for i in range(p-1):
            a = min(total_vote, m)
            b_list[-i-1] += a
            total_vote -= a
            if total_vote == 0:
                break
        
        for i in range(n-p+1):
            if i != x and b_list[x] > b_list[i]:
                a = min(total_vote, m, b_list[x] - b_list[i])
                b_list[i] += a
                total_vote -= a
                if total_vote == 0:
                    break

        if total_vote == 0:
            return True
        else:
            return False

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