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



Sample input:
6 1 2 2
2 1 1 3 0 2


Sample output:
5

Submission status: Runtime Error

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

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]


for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# calc p
p = P
for i in range(0, A[0]):

    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        p = i
        break

if p < 0:
    print(N)
    exit()

#print("p", p)
#print("NUM", NUM)


R = p + M
if R < 0:
    R = A[0] - A[len(A)-1]

ans = R
NG = N - ACN[R]
PNG = (N - ACN[R]) * M
m = M

#print("R", R)

'''
# PNG
for i in range(R+1, A[N-1]):
    if NUM[i] == 0:
        continue

    if M < (i-R):
        PNG += (N - ACN[i-1]) * M
        break

    PNG += NUM[i] * (i-R)
    NG_notall[(i-R)] = NUM[i]
'''

# loop
for r in range(R, -1, -1):
    m = M
    t = NUM[r]

    if t == 0:
        continue

    sm = M * V

    #print("r", r, "sm", sm, "PNG", PNG, "NUM", NUM[r])

    sm -= (r - p)*NUM[r]
    sm -= PNG
    m -= (r - p)

    if sm < 0:
        ans = r
        break

    rn = r
    for q in range(r-1, -1, -1):
        tq = NUM[q]
        if tq == 0:
            continue

        #t += tq

        if q < p:
            m -= (rn - q)

        if m < 0:
            PNG += NUM[r] * M
            break

        sm -= (rn - q) * t

        #print("q", q, "m", m, "sm", sm, "rn-q", (rn-q), "t", t)

        rn = q
        t += tq

        if sm < 0:
            ans = r
            break

    if sm < 0:
        ans = r
        break

    #print("sm", sm, "m", m)

    if m < 0:
        continue

    pr = p
    for j in range(len(NUM)):
        if NUM[j] == 0:
            continue

        pr -= NUM[j]
        sm -= NUM[j] * (M - j)

        if pr < 0:
            break

    if sm < 0:
        ans = r
        break
    else:
        PNG += NUM[r] * M


# print(ans)
print(ACN[r])

'''
    for q in range(p-1, -1, -1):
        tq = NUM[q]
        if tq == 0:
            continue

        t += tq
        sm -= (q - rn) * t
        rn = q

        if sm < 0:
            ans = r
            break
'''

Submission status: Runtime Error

Solution code:
import itertools
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
ans = p
a.sort(reverse=True)
def binary_search(left, right):
    if right - left <= 1:
        return left
    middle = (left + right) // 2
    if check(middle):
        return binary_search(middle, right)
    else:
        return binary_search(left, middle)

def check(target):
    used_vote = (p + n - target - 1) * m
    sum_vote = 0
    for i in range(target-1, p-2, -1):
        sum_vote += (a[target] + m) - a[i]
    if sum_vote >= m * v - used_vote: 
        return True
    else:
        return False

print(binary_search(0,n+1) + 1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
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()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    A = A[:-(P-1)]
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        C = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        # C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    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))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

left=0
right=n-p-1

while  right -left >1:
    mid =(left+right)//2
    if a[mid]+m < a[n-p]:
        left=mid
    else:
        j=v-(mid+1+p-1)
        if j <= 0:
            right=mid
        else:
            sum=0
            for k in range(mid+1,n-p+1,1):
                if m+a[mid]-a[k] < 0:
                    left = mid
                    break
                sum+=a[mid]+m-a[k]
                if sum >= j*m:
                    right=mid
                    break
                if k==n-p:
                    left=mid


p1 = 0
mid = left
if a[mid] + m < a[n - p]:
        p1 = 0
else:
        j = v - (mid + 1+p-1)
        if j <= 0:
            p1 = 1
        else:
            sum = 0
            for k in range(mid + 1, n+p+1, 1):
                if m + a[mid] - a[k] < 0:
                    p1 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p1 = 1
                    break
                if k == n-p:
                    p1 = 0
p2 = 0
mid = right
if a[mid] + m < a[n - p]:
        p1 = 0
else:
        j = v - (mid + 1 + p - 1)
        if j <= 0:
            p2 = 1
        else:
            sum = 0
            for k in range(mid + 1, n + p + 1, 1):
                if m + a[mid] - a[k] < 0:
                    p2 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p2 = 1
                    break
                if k == n - p:
                    p2 = 0

if left==right:
    if p1==1:
        print(n-left)
    else:
        print(n-left-1)
else:
    if p1==1:
        print(n-left)
    elif p2==1:
        print(n-left-1)
    else:
        print(n-left-2)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
pre = list(map(int, input().split()))
li = sorted(pre)
total = M * V
for i in range(N):
	if li[i] + M >= li[-P]:
		tmp = i+1 + P - 1
		nokori = total - (M * tmp)
        if N - tmp != 0:
			if li[i] + M > nokori // (N-tmp) + li[-P]:
				ans = N - i
				break
        else:
          ans = N-1
          break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,v,p = map(int,input().split())
A = list(map(int,input().split()))

B = {}
B[-1] = 0
A.sort()
for i in range(n):
    try:
        B[A[i]] += 1
    except:
        B[A[i]] = 1

A.sort(reverse=True)
b = A[p]
# print(b)
S = [0] * (len(B))
SS = list(B.values())

# print(SS)
S[-1] = SS[-1]
for i in range(len(SS)-2, -1, -1):
    S[i] = S[i+1] + SS[i]
    

# print("B",B)
# print(S)

ok = -1
c = 0

c2 = 0

D = {}
D[0] = -1
BK = list(B.keys())
# print(BK)
kk = 1
for i in range(len(BK)):
    if B[BK[i]] > 0:
        D[kk] = BK[i]
        kk += 1

# print("D",D)
l = -1
r = max(D.keys())+1
# print(l,r)
mi = (l+r)//2
while r-l > 1:
    c = D[mi]
    # print("mi",mi,"start")
    if c + m - b < 0:
        ok = 0
    
    else:
        c2 = c + m
        B[c] -= 1
        
        r = 0
        ii = len(SS)-1
        while D[ii] > c2:
            r += SS[ii]
            ii -= 1
        # print("r",r)
        koe = max(0,p-1-r)

        vall = max((v-1-r) * m, 0)
        # print("saisyo vall", vall)
        # print("c2",c2)
        for ii in range(len(D)-1,-1,-1):
            i = D[ii]
            if i < c2:
                if (c2-i)<m and koe > 0:
                    minus = m*B[i]
                    koe -= 1
                else:
                    minus = min(m*B[i], B[i]*(c2-i))
                vall -= minus
                # print(i,minus,koe,vall)
        # print("saigo vall",vall)
        
        if vall <= 0:
            ok = 1
        else:
            ok = 0
        B[c] += 1
    # print("mi",mi,"ok",ok)
    if ok == 0:
        l = mi
    else:
        r = mi
    mi = (l+r)//2
# print("l+1",l+1, "D", D[l+1])

# if l+1 <= max(D.keys()):
#     tt = D[l+1]
#     ans = sum(B[tt:])
# else:
#     ans = 0
# print(ans)
ans = 0
ii = len(SS)-1
while D[ii] >= D[l+1]:
    ans += SS[ii]
    ii -= 1
print(ans)

Submission status: Runtime Error

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

left=0
right=n-p-1

while  right -left >1:
    mid =(left+right)//2
    if a[mid]+m < a[n-p]:
        left=mid
    else:
        j=v-(mid+1+p-1)
        if j <= 0:
            right=mid
        else:
            sum=0
            for k in range(mid+1,n-p+1,1):
                if m+a[mid]-a[k] < 0:
                    left = mid
                    break
                sum+=a[mid]+m-a[k]
                if sum >= j*m:
                    right=mid
                    break
                if k==n-p:
                    left=mid

if left==right:
    print(n-left)
elif right-left==1:
    p1 = 0
    mid = left
    if a[mid] + m < a[n - p]:
        p1 = 0
    else:
        j = v - (mid + 1+p-1)
        if j <= 0:
            p1 = 1
        else:
            sum = 0
            for k in range(mid + 1, n+p+1, 1):
                if m + a[mid] - a[k] < 0:
                    p1 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p1 = 1
                    break
                if k == n-p:
                    p1 = 0
    p2 = 0
    mid = right
    if a[mid] + m < a[n - p]:
        p1 = 0
    else:
        j = v - (mid + 1 + p - 1)
        if j <= 0:
            p2 = 1
        else:
            sum = 0
            for k in range(mid + 1, n + p + 1, 1):
                if m + a[mid] - a[k] < 0:
                    p2 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p2 = 1
                    break
                if k == n - p:
                    p2 = 0

    if p1==1:
        print(n-left)
    elif p2==1:
        print(n-left-1)
    else:
        print(n-left-2)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
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()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    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))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import math
def handan(a,n,m,v,p,now):
    if v<=n-now+p-1:
        if a[p-1]<=a[now]+m:
            return True
        else:
            return False
    else:
        vv=v-(n-now+p-1) #>=1
        b =a[p-1:now]
        l=len(b)
        s=sum(b)
#        k_th=math.ceil((-l*a[now]+s)/(l-vv))
        kth=k_th(s,m,vv,l,a[now])
        if kth<=m:
            return True
        else:
            return False

left=0
right=n-1
ma=-1
while left<=right:
    now = (right+left)//2
    
    if handan(a,n,m,v,p,now):
        left = now+1
        if ma<=now:
            ma=now
    else:
        right = now-1
print(ma+1)

def k_th(s,m,vv,l,aa):
    left=0
    right=m
    mi=m+1
    while left<=right:
        now = (right+left)//2
        
        if math.ceil((s+vv*now)/l)<=aa+now:
            left = now+1
            if mi>=now:
                mi=now
        else:
            right = now-1
    return mi

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            # count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    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))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

score.sort(reverse=True)
non = N-P
boader = score[P-1]
maxadd = M
if V=>P:
    boader = score[V-P-1] + M
possiblescore = boader-maxadd
cannot = [i for i in score if i < possiblescore]

ans = N-int(len(cannot))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import Counter
from math import ceil

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

a.sort(reverse=True)
acm = list(accumulate(a))
c = Counter(a)
c = list(c.values())
#print(c)
always_ok = a[p-1]
cnt = 0
j = 0
prev = -1

for i, e in enumerate(a):
    if e != prev:
        cnt += c[j]
        j += 1
        prev = e
    if e >= always_ok:
        continue

    if n - i + p - 1 >= v:
        if e + m >= always_ok:
            continue
        else:
            #print(i, e, "break")
            break

    cnt -= c[j-1]
    #print(i, e)
    left = v - (n - i + p - 1)
    #print(left)
    sm = acm[i-1] - acm[cnt-1]
    #print(sm)
    mx = max(a[p-1], ceil((sm + left * m) / (i - cnt + 1)))
    #print(mx)
    cnt += c[j-1]
    if mx > e + m:
        break

cnt = 0
for ae in a:
    if ae == e:
        break
    cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a_ = a
for i in range(m):
  a = sorted(a)
  for j in range(v):
    a[j]+=1
  print(a)
b = sorted(a, reverse=True)
c = b[p-1]
d = [n+m for n in a_]
print(len([i for i in d if i >= c]))

Submission status: Runtime Error

Solution code:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok1(mid, val):
        if val >= A[mid]:
            return True
        else:
            return False

    def is_ok2(mid, val):
        if val > A[mid]:
            return True
        else:
            return False

    def binary_search_meguru(val, is_ok):
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid, val):
                right = mid
            else:
                left = mid
        return left

    not_ans = 0
    for i in range(N):
        top = A[i] + M
        upper = binary_search_meguru(top, is_ok1) + 1
        skip = 0
        if (-(V-1)) % N <= i+1:
            skip = 1
        if P <= upper:
            not_ans += 1
        elif A[-(V-1) + (P-1) - upper - skip] + M > top:
            top_less = P - 1
            top_less += max(0, N - binary_search_meguru(top, is_ok2) - 1)
            key = (V-1) - top_less
            mo = M % ((i-1)-(P-1))
            if i - mo <= key and top >= A[(P-1) + key] + M//((i-1)-(P-1) + 1) + 1:
                continue
            elif i - mo > key and top >= A[(P-1) + key] + M//((i-1)-(P-1) + 1):
                continue
            else:
                not_ans += 1

    print(N - not_ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
cnt = M*V
B = [[A[i],i] for i in range(N)]
for i in range(N):
    if cnt>=M:
        B[i][0] += M
        cnt -= M
    else:break
B = sorted(B,key=lambda x:x[1],reverse=True)
B = sorted(B,key=lambda x:x[0],reverse=True)
ind = B[P-1][1]
cur = P-1
while True:
    if B[cur+1][0]==B[cur][0]:
        ind = B[cur+1][1]
        cur += 1
    else:break
low = -1
high = ind
while high-low>1:
    mid = (high+low)//2
    cnt = M*V
    B = A[:]
    for i in range(mid+1):
        B[i] += M
        cnt -= M
    b = B[mid]
    for i in range(mid+1,N):
        if B[i]<b and cnt>=b-B[i]:
            B[i] += b-B[i]
            cnt -= b-B[i]
        else:break
    for i in range(N-1,-1,-1):
        if cnt>=M:
            B[i] += M
            cnt -= M
        elif 0<cnt<M:
            B[i] += cnt
            break
    ind = bisect_right(B,b)
    if N-ind<P:
        high = mid
    else:
        low = mid
print(N-high)

Submission status: Runtime Error

Solution code:
import bisect

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

List=list(map(int,input().split()))
List.sort()

a = List[P-1]
index = bisect.bisect_right(List, a) 

List.sort(reverse=True)
index = N - index

zako = N-(index+1)
tuyo = List[:index]
ans = len(tuyo)

if ans > P:
  if ans - P < N -V:
    bar = min(tuyo) - M
  else:
    bar = min(tuyo) - M  +1
else:
  bar = min(tuyo) - M

List.sort()
index = bisect.bisect_left(List, bar)

length = len(List)
a = length-index
print(int(min(a,V)))

Submission status: Runtime Error

Solution code:
n=int(input())
a,b=map(str,input().split())
c=""
for i in range(n):
  c+=a[i]
  c+=b[i]
print(c)

Submission status: Runtime Error

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

a.sort(reverse=True)
# a = np.array(a)

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)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
pre = list(map(int, input().split()))
li = sorted(pre)
total = M * V
for i in range(N):
	if li[i] + M >= li[-P]:
		tmp = i+1 + P - 1
		nokori = total - (M * tmp)
		if li[i] + M > nokori // (N-tmp) + li[-P]:
			ans = N - i
			break
print(ans)

Submission status: Runtime Error

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

score.sort(reverse=True)
non = N-P
boader = score[P-1]
maxadd = M
if V-non <= P:
    boader = score[P+(V-non)-1] + M
possiblescore = boader-maxadd
cannot = [i for i in score if i < possiblescore]

ans = N-int(len(cannot))
print(ans)

Submission status: Runtime Error

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

#A = [[int(i),x]for x,i in enumerate(input().split())]

maxA = max(A)
amount = A.count(maxA)
numorder = sorted(list(set(A)),reverse = True)
target = P - amount

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  Y = [k for k in A if k < x]
  y = len(Y)

  if y > V - 1:
    if x >= numorder[target]:
      con += 1
  else:
    Z = [j for j in A if j >= x]
    z = len(Z)

    if V - y < z and target + 1 > z:
      con += 1

print(con)

Submission status: Runtime Error

Solution code:
import itertools
import copy

N, M, V, P = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]

patterns = itertools.combinations(range(N), V)
combinations = itertools.combinations_with_replacement(patterns, M)

apparentlist = []
for combination in combinations:
    A_cal = copy.copy(A)
    for pattern in combination:
        for row in pattern:
            A_cal[row] += 1
    A_sort = sorted(A_cal, reverse=True)
    for i in range(N):
        if A_cal[i] >= A_sort[P-1]:
            apparentlist.append(i)

print(len(set(apparentlist)))

Submission status: Runtime Error

Solution code:
import math
N,A,B = map(int,input().split())
if abs(B-A+1)%2 ==1 :
    print(math.ceil(abs(B-A)/2))
 
elif abs(B-A+1)%2==0:
    if B <= math.ceil(N/2):
        print(B-1)
    elif A >= math.ceil(N/2):
        print(N-A)
    if B-1 >= N-A :
        print(math.ceil(-1*A+B-1))

    if B-1 < N-A :
        print(math.ceil((B-A-2)/2))

Submission status: Runtime Error

Solution code:
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
B = M * V
C = (P-1) * M
k = 0 #A[P-1]と同じやつの数
while A[P-1] == A[P-1+(k+1)]:
  k += 1

def ans(a,N,M,P,A,B,C,k):
  t = 0 #切り捨てる数（後ろから）
  z = 0
  while A[P-1]+a-M > A[N-1-t]:
    t += 1
  D = B - C - t*M
  #print(D)
  for i in range(P-1,N-t):
    z += A[i]
  y = (A[P-1]+a)*((N-t)-P+1) - z #きれいに埋めるのに必要な数
  if D <= y-(((N+t)-P+1)-(k+1)):
    print(P+k)
    exit()
  elif y-(((N+t)-P+1)-(k+1)) < D <= y:
    print(N-t)
    exit()
  elif D > y:
    ans(a+1,N,M,P,A,B,C,k)
ans(0,N,M,P,A,B,C,k)

Submission status: Runtime Error

Solution code:
impo=0
for i in range(n):
    #print(al[i])
    if al[-p]!=al[i]:
        if v-i-1 < p: # p番目に大き物には足されない
            if al[i]+m < al[-p]: 
                impo+=1   
            else:
                break
        else:
            comp=0
            for j in al[i+1:-p]:
                comp+=j
            if float(al[i]+m)<= float((comp+m*(v-p-i))/len(al[i+1:-p])):
                impo+=1
            else:    
                break
    else:
        break
print(n-impo)

Submission status: Runtime Error

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

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

def check(num):
    global n, a, m, v, p, l
    if num >= n - 1 - p:
        return True
    idx = bisect.bisect_left(a, a[num]+m)
    sum_ = l[idx] - a[num]
    idx -= 1
    if idx == 0:
        return False
    if a[num] + m >= math.ceil((m * min(v - (p - 1), (n - idx)) + sum_) / idx):
        return True
    else:
        return False

if check(0):
    print(n)

for i in range(n-1):
    if not check(i) and check(i+1):
        print(n - i - 1)
        exit()

Submission status: Runtime Error

Solution code:
n,m,v,p = map(int,input().split())
l = sorted(list(map(int,input().split())))[::-1]
a=0
f=[]
d=[]
c=1
for i in range(1,n):
  if l[i]!=l[i-1]:
    f.append(c)
    d.append(l[i-1])
    c=1
  else:
    c+=1
f.append(c)
d.append(l[n-1])
k = 0
for i in range(len(f)):
  k+=f[i]
  if k>=p:
    break
a=k
x = i
k = 0
for i in range(len(f)-1,-1,-1):
  k+=f[i]
  if k>=v:
    break
y = i
if v==n-1:
  print(a)
  exit()
for i in range(n-1,n-2-len(f),-1):
  l[i]+=m
j = sorted(l)[::-1][p+1]
for i in range(x+1,len(d)):
  if d[i]+m>=j:
    a+=f[i]
  else:
    break
print(a)

Submission status: Runtime Error

Solution code:
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse=True)
for i in range(p)[::-1]:
  if a[p-1] < a[i]:
    k = i + 1
    break
ans = p
d = 0
t = 0
for i in range(p, n):
  if a[i-1] == a[i]:
    ans += 1
    t += d
    #d += d
  else:
    if k + n - (i + 1) >= v - 1:
      #print(p,k,n,i,v,d)
      if a[i-1] - a[i] <= m-d:
        ans += 1
        d += a[i-1] - a[i]
        t += d
      else:
        break
    else:
      if (m * (v - 1 - (k + n - (i + 1))) - t - 0.1) // (i-k) + 1 + a[p] <= a[i] + m:
        ans += 1
        d += a[i-1] - a[i]
        t += d
      else:
        break
  #print(ans,i)

print(ans)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
t = 0
i = 0
while t == 0:
  i += 1
  if A[N-P-i] * M >= A[N-P]:
    if V <= N-i :
      true
    else:
      if A[N-P] * (i-1) - sum(A[N-P-i+1:N-P])  >= M * (V-N+i-1):
        true
      else:
        t = 1
  else:
      t = 1
print(P + i - 1)