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
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, V, P, A):
    A.sort(reverse=True)
    def f(i):
        if i < P:
            return 0

        if V - P <= 0:
            if A[i] + M >= A[P-1]:
                return 0
            else:
                return 1
        else:
            am = A[i] + M
            r = V - P
            B = []
            for j in range(P-1, N):
                if j != i:
                    B.append(A[j])
                j += 1
            heapq.heapify(B)
            C = []
            rm = M * r
            while B:
                b = heapq.heappop(B)
                d  = am - b
                if d > 0:
                    if d > M:
                        d = M
                    if d <= rm:
                        rm -= d
                        C.append(b+d)
                    else:
                        C.append(b+rm)
                        rm = 0
                else:
                    C.append(b)
            return 0 if max(C) <= am and rm == 0 else 1

    b = Bisect(f)
    i = b.bisect_right(0.5, lo=0, hi=N)
    return i


def main():
    N, M, V, P = read_int_n()
    A = read_int_n()
    print(slv(N, M, V, P, A))

    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
n, m, v, p = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = -np.sort(-a)
rest = a[p-1:]
sa = np.cumsum(rest)
nr = len(sa)
ans = p
r0 = rest[0]

for i, (sl, ai) in enumerate(zip(sa, rest)):
    if i == 0:
        continue
    nsmalls = nr-i
    nlarges = i
    rm = max(v-nsmalls-(p-1), 0)
    slarges = sl+rm*m-ai
    mean_larges = slarges/nlarges
    aim = ai+m
    if mean_larges <= aim and r0 <= aim:
        ans += 1
    else:
        break
print(ans)

Solution (Python):
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N, M, V, P = rl() 
A = rl()
A.sort(reverse=True)
INF = 10 ** 10
A = A[P-1:] + [-INF] 
V -= (P-1)
N = len(A)
answer = P-1


high = N-1 
low = 0 
while high > low + 1:
    mid = (high+low)//2
    num = max(0, V - (N-1-mid)) 
    B = np.array(A[:mid])
    
    count = ((A[mid] + M) - B).sum()
    if count <  M * num:
        high = mid 
    
    elif A[0] > A[mid] + M:
        high = mid
    else:
        low = mid

answer += (low + 1)
print(answer)

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

import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    A.sort(reverse = True)

    used_vote = (P-1)*M
    res = M*V-used_vote

    
    a = A[P-1:]
    r = a[0]+1
    l = -1
    while r - l > 1:
        mid = (r+l)//2
        goal = mid+M

        
        if a[0] > goal:
            l = mid
            continue

        need= 0 
        for aa in a:
            need+=min(M,goal-aa)
        
        if need >=res: 
            r = mid
        else:
            l = mid
    
    
    for i in range(N):
        if A[i] > l:
            continue
        else:
            print(i)
            return
    print(N)
    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()


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):
import bisect
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
wa = [a[0]]
for i in range(1,n):
    wa.append( wa[i-1] + a[i] )
border = a[n-p]
j = bisect.bisect_right(a,border)
for i in range(n):
    if a[i] + m >= border:
        if n-j+i+1 >= v:
            print(n-i)
            break
        else:
            if (j-i-1)*(a[i]+m)-(wa[j-1]-wa[i]) >= (v-(n-j+i+1))*m:
                print(n-i)
                break

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

a = sorted(a)[::-1]

minp = a[p-1]
result = 0
td = 0
count = 0
tpcount = 1
tptd = 0
pre = minp
for i in range(p, n):
    if pre != a[i]:
        td += tptd
        count += tpcount
        tptd = 0
        tpcount = 0
    if m * min(n-v, count) >= (minp - a[i]) * count - td and minp <= a[i] + m:
        result+=1
        tpcount+=1
        tptd+= minp - a[i]
        pre = a[i]
    else:
        break
print(result+p)

Solution (Python):

import numpy as np
N, M, V, P = map(int, input().split())
A = np.array(input().split(), dtype=int)

A = np.sort(A)[::-1]


def f(X):
    
    if (A[P-1] > A[X-1] + M):
        
        return False

    
    V2 = V - (P-1) - 1 - (N-X)
    if V2 < 0: V2 = 0
    
    
    Ax = A[X-1] + M
    RANGE = Ax - A[P-1:X-1]
    
    
    
    
    RANGE = np.minimum(RANGE, M)
    
    
    return np.sum(RANGE) >= M*V2


lo, up = P, N

while(lo!=up):
    ta = (lo + up + 1) // 2
    

    if f(ta):
        lo = ta
    else:
        up = ta - 1

print(lo)

Solution (Python):
from itertools import accumulate
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
I = P
for i, a in enumerate(A[P:], P+1):
    if a + M >= A[P-1]:
        I = i
    else:
        break
J = K = P + N - V
B = [0] + list(accumulate(A))

for i in range(J+1, I+1):
    
    if (i - P) * (A[i-1] + M) - B[i-1] + B[P-1] < (i - J) * M:
        break
    K = i
print(min(I, K))

Solution (Python):
def main():
    from bisect import bisect_left, bisect_right
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    N, M, V, P = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    acc = (0,) + tuple(accumulate(A))

    def is_ok(mid):
        x = A[mid]
        ika = bisect_right(A, x)
        rest = max(0, V - ika)
        if rest >= P:
            
            
            rng = N - ika - (P - 1) 
            times = V - (P - 1) - ika 

            range_sum = acc[mid + 1 + rng] - acc[mid + 1]
            to_sub = A[mid + rng] * rng - range_sum
            to_dist = M * times - to_sub

            if to_dist <= 0:
                return A[N - P] <= x + M
            else:
                to_add = (to_dist + rng - 1) // rng
                return max(A[N - P], A[mid + rng] + to_add) <= x + M

        else:
            return A[N - P] <= 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

    idx = binary_search()
    print(N - bisect_left(A, A[idx]))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
      prv_val = key
      prv_val_num = cntA[key]
  else:
    if last_val-key > M:break
    dif_val += (dif_num+prv_val_num)*(prv_val-key)
    dif_num += prv_val_num
    if dif_val <= (N-V)*M:
      selected_num += cntA[key]
    else:break
    prv_val = key
    prv_val_num = cntA[key]
    
print(selected_num)

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

A.sort(reverse  = True)

B = [0]
b = 0

for i in range(N):
    b+=A[i]
    B.append(b)

count = 0

def bisect(x,l,r):
    if A[l]<=x:
        return l-1
    elif A[r]>x:
        return r
    while r-l > 1:
        if A[(l+r)//2]>x:
            l = (l+r)//2
        else:
            r = (l+r)//2
    return l

for i in range(N):
    if i <= N-V+P-1:
        if A[i]+M>=A[P-1]:
            count+=1
    else:
        if A[i]+M>=A[P-1]:
            """
            index = bisect(A[i]+M,0,i-1)
            if index==-1:
                if (i*(A[i]+M) - B[i])%(V-(N-i)) == 0:
                    if (i*(A[i]+M) - B[i])//(V-(N-i)) >= M:
                        count+=1
                        print(A[i])
                else:
                    if (i*(A[i]+M) - B[i])//(V-(N-i)) >= M-1:
                        count+=1
                        print(A[i])
            else:
                if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))%(V-(N-i)-(index+1)) == 0:
                    if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))//(V-(N-i)-(index+1)) >= M:
                        count+=1
                        print(A[i])
                else:
                    if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))//(V-(N-i)-(index+1)) >= M-1:
                        count+=1
                        print(A[i])
            """
            
            
            
            if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))%(V-(N-i)-(P-1)) == 0:
                if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))//(V-(N-i)-(P-1)) >= M:
                    count+=1
            else:
                if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))//(V-(N-i)-(P-1)) >= M:
                    count+=1

print(count)

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

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R
table = [0]*N
for i in range(L, R):
    table[i] = K - A[i]
table2 = [0]*N
for i in range(L, R):
    table2[i] = table2[i-1] + table[i]

X = table2[R-1]

for i in range(L, R):
    
    if V > P+i:
        v = V - (P+i)
        D = N-P - i
        
        if (-((-(v*M - (X - table2[i]))) // D)) + K <= A[i]+M:
            ans += 1

    else:
        ans += 1

print(ans)

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)
 
lim_A = A[p-1]
res_A = A[p:]
res_n = len(res_A)
 
for i in range(res_n):
    res_A[i] = lim_A - res_A[i]
 
ans = p
cnt = 0
for i in range(res_n):
    if m >= res_A[i] and m * max(v-p-(res_n-i-1), 0) <= cnt + (m-res_A[i])*(i+1):
        ans += 1
    cnt += res_A[i]
 
print(ans)

Solution (Python):
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
kijun=a[p-1]
s=[0]*n
for i in range(n):
  s[i]+=s[i-1]+a[n-i-1]
if p>=v:
  print(n-bisect.bisect_left(a[::-1],kijun-m))
else:
  for i in range(n)[::-1]:
    rem=m*max(0,v-(n-i+p-1))
    if rem+(s[n-p]-s[n-1-i]) <= (a[i]+m)*(i-p+1) and a[i]+m >= kijun:
      print(i+1)
      break
    else:
      pass

Solution (Python):
import sys
input = sys.stdin.readline
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def judge(i):
    thres = a[i] + m
    rem = m * v - (n - i) * m
    rank = 0
    memo = 0
    for j in range(i):
        if a[j] > thres:
            rank += 1
            rem = max(rem-m, 0)
        else:
            if rank < p-1:
                rank += 1
                rem = max(rem-m, 0)
            else:
                rem = max(rem-(thres-a[j]), 0)
        if rank > p -1:
            break
    
    if rank <= p - 1 and rem == 0:
        return True
    else:
        return False
l = 0
r = n-1

while True:
    if r - l == 1:
        if judge(r):
            print(r+1)
        else:
            print(l+1)
        break
    i = (r + l) // 2
    if judge(i):
        l = i
    else:
        r = i

Solution (Python):
from bisect import bisect_left

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]

if V <= P:
    tmp = bisect_left(A[:-P], A[-P] - M)
    print (N - tmp)
    exit()

v = V - (P - 1) 


def check(x):
    if A[x] + M < A[-P]:
        return False
    if v - 1 <= x:
        return True
    
    zan = M * (v - (x + 1))
    
    if x > 0:
        used = B[-P] - B[x]
    else:
        used = B[-P]
    
    if (A[x] + M) * ((N - P) - x) - used >= zan:
        return True
    return False     


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


if check(l):
    print (N - l)
    exit()
if check(r):
    print (N - r)

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

def check(mid):
    remain = v*m
    more = 0
    less = 0
    same = 0
    tmp = [0]
    for i in range(n):
        if a[i]+m <= a[mid]+m:
            less += 1
            remain -= m
        elif a[i]<=a[mid]+m:
            same += 1
            remain -= a[mid]+m-a[i]
            tmp.append(tmp[-1] + a[i]-a[mid])
        else:
            more += 1
            remain -= m
    if more >= p:
        return False
    if remain <= 0:
        return True
    hoge = p-more-1
    if (len(tmp) >= hoge+1 and tmp[hoge] >= remain) or (len(tmp) < hoge+1 and tmp[-1] >= remain):
        return True
    return False

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

print(left+1)

Solution (Python):
def check(n):
    x = A[n] + M
    if P == 1:
        B = A[:n] + A[n+1:]
    else:
        B = A[:n] + A[n+1:-(P-1)]
    scores = M * (V - P)
    if x < B[-1]:
        return False
    for b in B:
        if b + M <= x:
            scores -= M
        else:
            scores -= x - b
        if scores <= 0:
            return True
    return False


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

left = 0
right = N - P
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)

Solution (Python):
def check(i, N, M, V, P, A):
    K = N - V
    tot = sum(A[(P-1):i]) - A[i]*(i-(P-1))
    if K*M >= tot and (A[P-1]-A[i])<=M:
        return True
    else:
        return False

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

start = P
end = N-1
if check(end, N, M, V, P, A):
    print(N)
elif not check(start, N, M, V, P, A):
    print(P)
else:
    while True:
        if (end - start) == 1:
            break
        new = (start + end)//2
        flag = check(new, N, M, V, P, A)
        if flag:
            start = new
        else:
            end = new
    print(start+1)

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

se=set()
for i in range(p):se.add(a[i])

s=a[p-1]
for i in range(p,n):
  x=max(v-(n-((i+1)-(p-1)))-1,0)
  if a[i]+m>=max(0--(s+m*x)//(i-p+1),a[p-1]):se.add(a[i])
  
  s+=a[i]

ans=0
for i in a:
  if i in se:ans+=1
print(ans)

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

a.sort()
a = a[::-1]

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

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

        else:
            if v - p <= n - i:
                if a[i - 1] + m >= a[p - 1]:
                    ans += 1
            else:
                if a[i - 1] + m < a[p - 1]:
                    continue
                elif a[i-1] * (i - p) >= m * (v - n) + s[i - 2]:
                    ans += 1

print(ans)

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 math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res




n,m,v,p = list(map(int, input().split()))
aa = list(map(int, input().split()))
a = [[aa[i],i+1] for i in range(n)]

a.sort(key=lambda x:x[0])

b = [a[i][0] for i in range(n)]
anum = [a[i][1] for i in range(n)]


sums = []
now = 0
for i in range(n):
    now += b[i]
    sums.append(now)

ans = 0

firstMove = 1
for i in range(100):
    if(firstMove < n/2+0.1):
        firstMove*=2
    else:
        break

migis = []
'''

for i in range(n):
    tall = b[i]+m
    
    now = i
    move = firstMove
    while(move!=0):
        if(now+move < n):
            if(tall >= b[now+move]):
                now += move
        move = move//2
        
    migis.append(now)

'''
for i in range(n):
    if(i >= n-p):
        ans+=1
        continue
    if(b[i]+m < b[n-p]):
        continue
    k = b[i]+m
    amount = 0
    amount += m * (i+1)
    
    
    amount += m * (p-1)
    
    amount += (b[i]+m)*(n-p-i)-(sums[n-p]-sums[i])
    
    
    
    
    if(amount < m*v):
        continue
    else:
        ans+=1
        
        continue

print(ans)

Solution (Python):
n,m,v,p=map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
reva = [a[0] - x for x in a]
ub = a[0]
lb = a[-1]

from bisect import *

def ok(val):
    i = bisect_left(reva,a[0]-val)
    val = a[i]
    if v-(min(n-i,v)) < p and a[p-1] <= a[i] + m:
        return True
    l = v - (p-1) - (n - i)
    if a[i]+m < a[p-1]:
        return False
    if sum(list(map(lambda x:min(a[i]+m-x,m),a[p-1:i]))) >= l*m:
        return True
    return False

while ub > lb:
    mid = (ub+lb)//2
    if ok(mid):
        ub=mid
    else:
        lb=mid+1

print(len(list(filter(lambda x:x >= lb,a))))

Solution (Python):
def solve(n, m, v, p, a_list):
    a_list_s = sorted(a_list, reverse=True)
    
    
    
    base_bar = a_list_s[p - 1]
    res = p
    space = 0
    for i in range(p, n):
        if a_list_s[i] + m - base_bar < 0:
            break
        space_now = space + (a_list_s[i] + m - base_bar) * (i - p + 1)
        v_now = max(v - (n - i) - (p - 1), 0)
        if space_now >= v_now * m:
            res += 1
        space += base_bar - a_list_s[i]

    return res


def main():
    n, m, v, p = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, m, v, p, a_list)
    print(res)


def test():
    assert solve(6, 1, 2, 2, [2, 1, 1, 3, 0, 2]) == 5
    assert solve(6, 1, 5, 2, [2, 1, 1, 3, 0, 2]) == 3
    assert solve(10, 4, 8, 5, [7, 2, 3, 6, 1, 6, 5, 4, 6, 5]) == 8


if __name__ == "__main__":
    test()
    main()

Solution (Python):
N,M,V,P=[int(a) for a in input().split()]
A=[int(a) for a in input().split()]
effect=N-V
A.sort(reverse=True)

ans=P
target_score=A[P-1]
target_vote=0
to_kill=0

for i in range(P,N):
    if A[i-1]>A[i]:
        
        target_vote+=(A[i-1]-A[i])*(i-P+1)
        to_kill=i-P+1
        
    real_effect=min(effect,to_kill)
    
    if target_vote==0 or (((target_vote-1)//real_effect)+1<=M and target_score-A[i]<=M):
        ans+=1
    
print(ans)

Solution (Python):
import bisect
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, M, V, P = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A.sort(reverse=True)
RA = A[::-1]


def can_choose(k):
    
    ak = A[k] + M
    greaters = N - bisect.bisect_right(RA, ak)
    if greaters >= P:
        return False
    
    rem = (V - P) * M

    cnt = 0
    for i, a in reversed(list(enumerate(A))):
        if i == k:
            continue
        if rem <= 0:
            break
        rem -= min(M, ak - a)

        cnt += 1
        if cnt >= N - P:
            break
    return rem <= 0








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

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

a.sort()
ans = p-1
end = n-p+1
loopend = n-v+1
sm = sum(a[0:end])
needed = (v - (p-1)) * m

for i in range(end):
    sm -= a[i]
    needed -= m
    if a[i] + m < a[end-1]:
        continue
    max_score = (a[i] + m) * (end-i-1) - sm
    
    
    if needed <= max_score:
        ans = n-i
        break
print(ans)

Solution (Python):




def check(A, M, V, P, idx):
  
  v = A[idx] + M

  if v < A[P]:
    
    return False

  n = M * (V - P - (len(A) - idx))

  if n <= 0:
    
    return True

  r = sum(v - x for x in A[P:idx])

  
  return r >= n


def main():
  _, M, V, P = map(int, input().split())
  A = sorted(list(map(int, input().split())), reverse=True)
  P -= 1

  if check(A, M, V, P, len(A) - 1):
    print(len(A))
    return

  low = P
  high = len(A) - 1

  while (high - low) > 1:
    idx = (low + high) // 2
    ret = check(A, M, V, P, idx)

    if ret:
      low = idx
    else:
      high = idx

  print(high)


if __name__ == '__main__':
  main()

Solution (Python):
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=p
S=[A[p-1]]
for i in range(p,n):
    S.append(S[-1]+A[i])
for i in range(p,n):
    if v<=p+n-i-1:
        if A[p-1]-A[i]<=m:
            ans+=1
    else:
        if A[p-1]-A[i]<=m and S[i-p]-A[i]*(i-p+1)<=(n-v)*m:
            ans+=1
        else:
            break
print(ans)

Solution (Python):

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

As = sorted(A)
border = As[-P]
upbound = N-P
lowbound = N-P
while As[upbound] == border:
    upbound += 1
    if upbound > N-1:break
while As[lowbound] == border:
    lowbound -= 1
    if lowbound < 0:break

upbound -= 1
lowbound += 1
    
def isOK(mid):
    if mid>= lowbound: return True
    if mid==N-1: return True
    if (border-As[mid])>M:
        return False
    
    S = sum(As[mid+1:upbound+1])-As[mid]*(upbound-mid)
    U = M*(N-V)
    if S>U:
        return False
    else:
        return True

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


key = bsearch()

print(N-key)

Solution (Python):
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
c = a[p-1]


b = 0
d = 0
ans = 0
for i in range(n):
  if i < p-1:
    ans += 1
    continue
  if a[i] + m < c:
    continue
  now = a[i]
  vv = v - (n-i) - (p-1)
  
  if vv <= 0 or d * (now+m) >= b + vv * m:
    ans += 1
  b += now
  d += 1
print(ans)

Solution (Python):
def judge(ind):

    maxi = A[ind] + M

    left = M * (V-1)
    over = 0
    np = P-1

    for i in range(N):
        
        if i == ind:
            continue
        
        if np > 0:
            left -= M
            np -= 1
        elif A[i] > maxi:
            return False
        else:
            left -= min(M, maxi - A[i])

    if left > 0:
        return False
    else:
        return True


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

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

A.sort()
A.reverse()

l = 0
r = N

while r - l != 1:

    mid = (l+r)//2

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

print (r)

Solution (Python):
import sys
input=sys.stdin.readline
n,m,v,p=map(int,input().split())
a_list=list(map(int,input().split()))
a_list.sort(reverse=True)
ans=p
S=0
for k in range(p+1,n+1):
    S+=a_list[k-2]
    if n-k+p>=v:
        if a_list[k-1]+m>=a_list[p-1]:
            ans+=1
    else:
        if a_list[k-1]+m>=a_list[p-1]:
            d=(k-p)*(a_list[k-1]+m)-S
            if (v-n+k-p)*m<=d:
                ans+=1
print(ans)

Solution (Python):
from bisect import bisect_right as br
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=n,-1
while l-r>1:
    t=(l+r)//2
    s=a[t]+m
    w=a[:]
    k=m*(v-1)
    for i in range(n):
        if i!=t:
            if i<t:
                c=min(k,m)
                k-=c
                w[i]+=c
            else:
                if w[i]>=s:
                    break
                else:
                    c=min(k,s-w[i])
                    k-=c
                    w[i]+=c
        if k==0:
            break
    if k>0:
        for j in range(n-1,-1,-1):
            if j!=t:
                g=min(k,m-w[j]+a[j])
                w[j]+=g
                k-=g
            if k==0:
                break
    w.pop(t)
    w=sorted(w)
    if n-br(w,s)<=p:
        l=t
    else:
        r=t
print(n-l)

Solution (Python):
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
S = sum(A)
for i in range(P-1):
    x = A.pop()
    S -= x
total_score = M*(V-P+1)
kazu = N - P + 1
for i in range(N-P+1):
    a = A.pop(0)
    total_score -= M
    S -= a
    kazu -= 1
    T = (M+a)*kazu - S
    if i == N - P:
        ans = P
    else:
        if (a+M) >= A[-1]:
            if T >= total_score:
                ans = kazu + P
                break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m, v, p = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
a.sort()
cumsum = [0] * (n+1)
for i in range(n):
    cumsum[i+1] = cumsum[i] + a[i]

hand = n - v 
ok = [0] * (n - p)
for i in range(n - p):
    total = cumsum[n-p+1] - cumsum[i+1] - a[i] * (n - p - i)
    maxval = a[n-p] - a[i]
    turn = max((total + hand - 1) // hand, maxval)
    if m >= turn:
        ok[i] = 1
ans = sum(ok) + p
print(ans)