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 = 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-right)//2
    if isOK(mid):  
        left = mid
    else:  
        right = mid
print(left + 1)

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

A.sort()

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

def check(m) :
  if m >= N - P :
    return True
  if A[m] + M < A[N - P] :
    return False

  rest = M * (V - P)
  x = A[m] + M
  for i in range(N - P + 1) :
    if i == m :
      continue
    rest -= min(x - A[i], M)
  return rest <= 0

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

print(N - ng - 1)

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

def isOk(n):
    if n < P:
        return True
    b = A[n] + M

    cnt = (P - 1) * M + (N - n) * M
    for a in A[P - 1: n]:
        cnt += max(0, b - a)

    if b >= A[P - 1] and cnt >= V * M:
        return True
    return False

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

print(ng)

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

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

print(ng)

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

ok, ng = p-1, n
while ng-ok > 1:
	mi = (ng+ok)//2
	possible = True
	x = a[mi]
	i = mi-1
	cnt = 0
	while i >= p-1:
		if a[i]-x > m:
			possible = False
			break
		cnt += a[i]-x
		i -= 1
	if cnt > m * (n - v):
		possible = False

	if possible:
		ok = mi
	else:
		ng = mi

print(ok+1)

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

A.sort()

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

def check(m) :
  if m >= N - P :
    return True
  if A[m] + M < A[N - P] :
    return False

  rest = M * (V - P)
  x = A[m] + M
  for i in range(N - P + 1) :
    if i == m :
      continue
    rest -= min(x - A[i], M)
  return rest <= 0

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

print(N - ng - 1)

Solution (Python):
n = input()    
m = n.split()
p = [int(i) for i in m]
n = input()    
m = n.split()
P = [int(i) for i in m]
nP = sorted(P,reverse=True)
A = p[3] -1
a = nP[p[3]-1]
sum = nP[p[3]-1]
V = a
for i, value in enumerate(nP):
    if i < p[3]:
        pass
    else:
        if V == value:
            sum = sum + value
            A = i
        else:
            if value + p[1] >= a:
                if ((i - p[3]+1)-(p[0] - p[2])) *p[1] <= (value +p[1])*(i - p[3]+1)-sum:
                    A = i
                    sum = sum + value
                    V = value
                else:
                    break
            else:
                break

print(A + 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()
l = -1
r = N
while r - l > 1:
    m = (l+r)//2
    if m+1+P > N:
        r = m
        continue
    if V <= m+P:
        if A[m]+M >= A[-P]:
            r = m
        else:
            l = m
        continue
    if A[m]+M < A[-P]:
        l = m
        continue
    limit = A[m] + M
    can = 0
    for i in range(m+1, N-P+1):
        can += limit-A[i]
    if can >= (V-P-m)*M:
        r = m
    else:
        l = m

print(N-r)

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


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

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


A_P = A[P-1]
A_X = A[P]
i_X = P
for i in range(P, len(A)):
    if (A_P - A[i]) > M:
        A_X = A[i-1]
        i_X = i-1
        break
    elif i == (len(A)-1):
        A_X = A[i]
        i_X = i
    else:
        continue

NG_POINT = (P-1) * M


def isPossible(i):
    if (i+1) < P:
        return True
    elif i > i_X:
        return False

    MV = M * V
    ax = A[i]
    score = ax + M

    total = M + NG_POINT
    total += (N - i - 1) * M

    for j in range(i-1, P-2, -1):
        total += score - A[j]

    

    if total >= MV:
        return True

    return False


left = 0
right = i_X

if not isPossible(left):
    print(1)
    exit()

if isPossible(i_X):
    print(i_X + 1)
    exit()



for _ in range(i_X):
    
    if (left + 1) == right:
        break

    mid = (left + right) // 2

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

print(left + 1)

Solution (Python):
from itertools import *
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
acc=list(accumulate(a))+[0]
ok,ng=p-1,n
while ng-ok>1:
	mid=(ok+ng)//2
	if a[mid]+m>=a[p-1] and (a[mid]+m)*(mid-p+1)-(acc[mid-1]-acc[p-2])>=m*(v-(p-1)-(n-mid)):
		ok=mid
	else:
		ng=mid
print(ok+1)

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

    def is_possible(i):
        
        
        

        
        if i < P:
            return True

        
        num_votes = V * M

        
        score_i = sorted_A[i] + M
        num_votes -= M

        
        if sorted_A[P - 1] > score_i:
            return False

        
        
        num_votes -= (N - i - 1) * M

        
        num_votes -= (P - 1) * M

        
        
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    
    
    if is_possible(N-1):
        print(N)

    
    
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            

        print(low + 1)


if __name__ == '__main__':
    main()

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

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

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M

        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)

Solution (Python):


import sys
import numpy as np


def check(N, M, V, P, As, i):
    
    border = As[P - 1]
    a = As[i]
    
    if a >= border:
        return True
    
    if a + M < border:
        return False

    
    num = M  
    num += (P - 1) * M  
    num += (N - i - 1) * M 
    for j in range(P - 1, i): 
        num += (a + M - As[j])
    
    return num >= M * V


def solve(N, M, V, P, As):

    As = As[:]
    As.sort(reverse=True)

    
    

    
    if check(N, M, V, P, As, N-1):
        return N

    ok = 0
    ng = N - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(N, M, V, P, As, mid):
            ok = mid
        else:
            ng = mid

    return ok + 1


def main():
    N, M, V, P = map(int, input().split())
    As = list(map(int, input().split()))
    print(solve(N, M, V, P, As))

main()

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

a.sort(reverse=True)


def can_be_used(x):
    
    if x < p:
        return True

    if a[x] + m < a[p-1]:
        return False

    vote_max = (p - 1 + n - x) * m
    for i in range(p-1, x):
        vote_max += a[x] + m - a[i]

    if vote_max < m * v:
        return False

    return True


l = 0
r = n

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

    if can_be_used(mid):
        l = mid
    else:
        r = mid

ans = l + 1
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    
    if cnt >= m*v:
        return True
    else:
        return False

ok = n-1
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ok)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    
    if cnt >= m*v:
        return True
    else:
        return False

ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ok)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    
    if cnt >= m*v:
        return True
    else:
        return False

ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ng-1)

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


def isPossible(i):
    
    i = A.index(A[i])

    
    if i < P:
        return True

    numVotes = V
    
    
    score = A[i] + M
    numVotes -= 1
    
    
    if A[P - 1] > score:
        return False
    
    
    numVotes -= N - i - 1
    
    
    numVotes -= P - 1
    if numVotes > 0:
        
        
        
        
        
        remainingVotes = numVotes * M
        gap = sum(score - x for x in A[P - 1 : i])
        return gap >= remainingVotes
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    
    
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    
    print(lo + 1)

Solution (Python):
from math import ceil
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)[p - 1:]
l = 0
r = n - p

while l != r:
    k = ceil((l + r) / 2)
    b = a[k] + m
    if b < a[0] or (v - (n - k)) * m > (k * b - sum(a[:k])):
        r = k - 1
    else:
        l = k
print(p+l)

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

As.sort(reverse=True)

scoreP = As[P-1]

def isOK(k):
    if k < P or As[k] == scoreP:
        return True

    scoreK = As[k] + M
    if scoreK < scoreP:
        return False

    rest = M*(V-1)
    rest -= M*(P-1)
    if rest <= 0:
        return True

    for i in range(P-1, N):
        if i != k:
            rest -= min(M, scoreK-As[i])
    if rest <= 0:
        return True

    return False


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok+1)

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

lst1.sort(reverse=True)

def func(u):
    score = lst1[u] + m
    cost1 = max(0,v-(n-u))*m
    all_score = (p-1)*m
    for i in range(p-1,u):
        if score-lst1[i] < 0:
            all_score = -1
            break
        all_score += score-lst1[i]
    if all_score >= cost1:
        return True
    else:
        return False  


def binary_search(n): 
    ok = p-1
    ng = len(lst1)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if func(mid):
            ok = mid
        else:
            ng = mid

    return ok

print(binary_search(n)+1)

Solution (Python):
import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(17):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))

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

A.sort(reverse=True)

S = [0]*N
t = 0
for i in range(N):
    t += A[i]
    S[i] = t

s = M*(N-V)
l = P
r = N
if P == 1:
    a = 0
else:
    a = S[P-2]
while l < r:
    m = (r-l)//2 + l
    if A[P-1]-M > A[m]:
        r = m
        continue
    if S[m-1]-a-(m-P+1)*A[m] > s:
        r = m
        continue
    l = m+1
    
print(l)

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

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

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

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

def check(i):
  if i <= P-1:
    return True
  vote = (V-1)*M
  vote -= (N-1-i)*M
  vote -= (P-1)*M
  if vote <= 0:
    return A[i]+M >= A[P-1]
  else:
    for j in range(i-1,P-1,-1):
      if A[j] > A[i]+M:
        return False
      v = min(A[i]+M-A[j],M,vote)
      vote -= v
      if vote <= 0:
        break
    if vote <= 0:
      return A[i]+M >= A[P-1]
    else:
      return A[i]+M >= A[P-1]+vote

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

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

prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
f = True


for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

while low < high:
    mid = (low + high) // 2
    if mid <= p-1:
        f = True
    elif prob_set[mid] + m < prob_set[p - 1]:
        f = False
    else:
        hyou = m * (p - 1) + m * (n - mid)
        for i in range(p-1,mid):
            hyou += prob_set[mid] + m - prob_set[i]
        
        
        
        
        if hyou < m*v:
            f = False
        else:
            f = True
    if f:
        low = mid + 1
    else:
        high = mid

print(high)

Solution (Python):
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
total = 0
target = A[p-1]
before_p = p - 1

ans = p-1
for idx in range(p-1, n):
    candidate = A[idx]

    if candidate + m < target:
        break

    later_idx = n - idx - 1
    if before_p + later_idx >= v - 1:
        ans += 1

    else:
        possible = (before_p + later_idx)*m
        possible += (candidate+m)*(idx-p+1) - total

        if possible >= m*(v-1):
            ans += 1
        else:
            break
    total += candidate

print(ans)

Solution (Python):
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True) + [-10 ** 10]
L, R, sA, lP = 0, N, [A[P - 1]], A[P - 1]
for i in range(P, N):
    sA.append(sA[-1] + A[i])

while R - L > 1:
    mid = L + (R - L) // 2
    if mid < P:
        L = mid
    elif A[mid] + M < lP:
        R = mid
    else:
        mi = mid - P + 1
        if M * (N - mi) + (A[mid] + M) * mi - sA[mi - 1] >= M * V:
            L = mid
        else:
            R = mid
print(L + 1)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s=[None]*N
t=0
for i in range(N):
    t+=A[i]
    s[i]=t
S=M*(N-V)
l=P
r=N
if P==1:
    a=0
else:
    a=s[P-2]
while l<r:
    m=(r - l) // 2 + l
    if A[P-1]-M>A[m]:
        r=m
        continue
    if s[m-1]-a-(m-P+1)*A[m]>S:
        r=m
        continue
    l=m+1
print(l)

Solution (Python):
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])): r=k
    else: l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)

Solution (Python):
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])):
        r=k
    else:
        l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)

Solution (Python):
import sys
n,m,v,p=map(int,sys.stdin.readline().split())
a=sorted(list(map(int, sys.stdin.readline().split())),reverse=True)[p-1:]
l,r=0,n-p

while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])):
        r=k
    else:
        l=k

b=a[r]+m
if b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r])):
    print(p+l)
else:
    print(p+r)

Solution (Python):
import sys
n,m,v,p=map(int,sys.stdin.readline().split())
a=sorted(list(map(int, sys.stdin.readline().split())),reverse=True)[p-1:]
l,r=0,n-p

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

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 sys
n,m,v,p=map(int,sys.stdin.readline().split())
a=list(map(int, sys.stdin.readline().split()))

a.sort(reverse=True)
a=a[p-1:]
l,r=0,n-p

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

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 sys
input=sys.stdin.readline
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
    b=a[x]+m
    if b<a[0]:
        return False
    al=(v-(n-x))*m
    s=x*b-sum(a[:x])
    return al<=s

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 sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()

    
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2

        if N-P <= mid:
            right = mid
            continue

        if A[mid]+M < A[N-P]:
            left = mid
            continue

        
        tot = 0
        for i in range(mid+1, N-P+1):
            tot += A[mid]+M-A[i]
        tot += (P-1)*M
        tot += mid*M
        tot += M

        if tot < M*V:
            left = mid
            continue
        else:
            right = mid
            continue

    print(N-bisect_left(A, A[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):
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
S = [0]
for i in range(N-P+1):
    S += [S[-1]+A[i]]
a = P-1
for i in range(N-P+1):
    if A[i]+M>=A[N-P] and A[i]*(N-P-i)-(S[-1]-S[i+1])>=M*(V-N):
        a += 1
print(a)

Solution (Python):
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = A[:N-P+1]

S = [0]
for i in range(N-P+1):
    S.append(S[-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[-1]-S[i+1])+M*(N-P)>=max(M*(V-P),0):
        ans += 1

print(ans)

Solution (Python):
N,M,V,P=map(int,input().split())
B = sorted(list(map(int, input().split())))[::-1]
count=P
dif=0
for i in range(P,N):
    dif+=B[i-1]
    if V<=(P-1)+(N-i) and B[P-1]<=B[i]+M:
        count+=1
    elif dif-B[i]*(i-P+1)<=M*(N-V) and B[P-1]<=B[i]+M:
        count+=1
print(count)

Solution (Python):


def solve(N: int, M: int, V: int, P: int, A: 'list[int]') -> int:
    """
    入れてよい票 < M*V
        M*V投票するとjを超えるスコアを持つ問題数がP以上になり、不可能

    入れてよい票 >= M*V
        可能

        次の条件を満たせば可能といえる
        
        
        
        投票してよい問題abc...zを
        許容される投票数だけ連続させた列(最大M=すべてのjudgeが投票した場合)
        aaaabbbcc...z
        仮定より長さMV以上なので,
        冒頭の区間(長さMV)に対し,judgeを0...M-1,0...M-1,...と割り当てることができる
        この割り当ては,3つの条件を満たす
    """

    from itertools import accumulate

    def is_ok(j):
        if j < P:
            return True
            

        X = A[j] + M  
        if X < A[P]:
            return False
            

        return (j - P) * X - (acc[j - 1] - acc[P - 1]) >= M * (V - (P + N - j))
        
        
        
        
        
        

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

    *A, = sorted(A, reverse=True)
    A = [0] + A  
    acc = tuple(accumulate(A))
    return binary_search()


def main():
    import sys
    input = sys.stdin.readline

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


if __name__ == '__main__':
    main()

Solution (Python):
def solve(N: int, M: int, V: int, P: int, A: 'list[int]') -> int:
    from itertools import accumulate

    def is_ok(j):
        from math import ceil

        X = A[j]
        always_add = (P - 1) + 1 + j  

        if V <= always_add:
            return A[N - P] <= X + M

        flat_distribute_block = N - always_add  
        count_per_judge = V - always_add  

        block_sum = acc[N - P + 1] - acc[j + 1]  
        without_exceed = A[N - P] * flat_distribute_block - block_sum  
        vote_piled_up = M * count_per_judge - without_exceed

        if vote_piled_up <= 0:
            return A[N - P] <= X + M
        else:
            to_add = ceil(vote_piled_up / flat_distribute_block)
            return A[N - P] + to_add <= X + M

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

    *A, = sorted(A)
    acc = (0,) + tuple(accumulate(A))
    return N - binary_search()


def main():
    import sys
    input = sys.stdin.readline

    N, M, V, P = map(int, input().split())
    A = map(int, input().split())
    print(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
import sys
import bisect
import string
import math
import time
from fractions import gcd



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 input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False



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
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

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

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = LI()
    A.sort()

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

    r = N - 1
    l = 0
    while r-l > 1:
        mid = (l+r) // 2
        
        if check(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        
    print(N - r)



if __name__ == '__main__':
    main()