Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02696 (python)

Fixed submission:
a,b,n=map(int,raw_input().split())
f=min(n,b-1)
print int((f*a)/b)

Buggy submission (verdict: Runtime Error):
a,b,n=map(int,raw_input().split())
f=min(n,b-1)
print int((f*a)/b)
Problem p02534 (python)

Fixed submission:
n = int(input())

output = 'ACL'*n
print(output)

Buggy submission (verdict: Runtime Error):
A,B,C,D = map(int, input().split())
 
x = list(range(A,B+1))
x = set(x)
y = list(range(C,D+1))
y = set(y)
 
if len(x)==0 or len(y)==0 or len(x&y)==0:
  print("No")
else:
  print("Yes")

Buggy submission (verdict: Runtime Error):
k = input()
output = "ACL" *k
print(output)
Problem p02610 (python)

Fixed submission:
import sys
from heapq import heappush, heappop, heappushpop

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

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))

Buggy submission (verdict: Runtime Error):
import sys
from heapq import heappush, heappop

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

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))
Problem p02614 (python)

Fixed submission:
import sys
import numpy as np

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

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'#')

def f(C, x, y):
    D = C.copy()
    for i in range(H):
        if x & (1 << i):
            D[i] = 0
    for i in range(W):
        if y & (1 << i):
            D[:, i] = 0
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

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

H, W, K = map(int, readline().split())
C = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

C = 1 * (C == b'#')

def f(C, x, y):
    rows = [bool(x & (1<<i)) for i in range(H)]
    cols = [bool(y & (1<<i)) for i in range(W)]
    D = C[rows, cols]
    return D.sum() == K

ans = 0
for x in range(1 << H):
    for y in range(1 << W):
        ans += f(C, x, y)
print(ans)
Problem p02616 (python)

Fixed submission:
import sys
import numpy as np

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    if len(pos) & 1:
        pos = pos[:-1]
    if len(neg) & 1:
        neg = neg[:-1]
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

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

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)
Problem p02642 (python)

Fixed submission:
import sys
import numpy as np
from numba import njit

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

@njit('(i4[::1],)', cache=True)
def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]

print(solve(A))

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np

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

U = 10**6 + 10

def main(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1],i8[::1])')(main)
    cc.compile()
    exit()
from my_module import main

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(solve(A, primes))
Problem p02677 (python)

Fixed submission:
import sys
from math import cos, sin, pi

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

A, B, H, M = map(int, read().split())

H += M / 60

t1 = 2 * pi * H / 12
t2 = 2 * pi * H

z1 = A * complex(cos(t1), sin(t1))
z2 = B * complex(cos(t2), sin(t2))

print(abs(z1 - z2))

Buggy submission (verdict: Runtime Error):
import sys
from math import exp, pi

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

A, B, H, M = map(int, read().split())

H += M / 60

t1 = 2 * pi * H / 12
t2 = 2 * pi * H

z1 = A * exp(t1 * 1j)
z2 = B * exp(t1 * 1j)

print(abs(z1 - z2))
Problem p02702 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('(i4[:],)')
def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(S):
    dp = [0] * 2019
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = [0] * 2019
        for i in range(x, 2019):
            newdp[x+i] += dp[i]
        for i in range(x):
            newdp[i] += dp[2019-x+i]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = [x - ord('0') for x in read().rstrip()]
print(solve(S))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np


def solve(S):
    dp = [0] * 2019
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        for i in range(x, 2019):
            newdp[x+i] += dp[i]
        for i in range(x):
            newdp[i] += dp[2019-x+i]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = [x - ord('0') for x in read().rstrip()]
print(solve(S))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('i4[:]')
def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))
Problem p02713 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

K = int(read())

x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
print(nums.sum())

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

K = int(read())

x = np.arange(1, K + 1)
nums = np.gcd.outer(x, x, x)
print(nums.sum())
Problem p02715 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9 + 7

N, K = map(int, read().split())

A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

for d in range(K, 0, -1):
    for i in range(2, K // d + 1):
        A[d] -= A[d * i]

answer = sum(d * x for d, x in enumerate(A))
print(answer % MOD)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 10**9 + 7
N, K = map(int, read().split())

is_prime = np.zeros(K + 1, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 1, 2):
    if p * p >= K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

for p in primes.tolist():
    for i in range(K // p + 1):
        A[i] -= A[i * p]

answer = sum(i * x for i, x in enumerate(A))
print(answer % MOD)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 10**9 + 7
N, K = map(int, read().split())

is_prime = np.zeros(K + 1, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 1, 2):
    if p * p >= K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

for p in primes.tolist():
    for i in range(N // p + 1):
        A[i] -= A[i * p]

answer = sum(i * x for i, x in enumerate(A))
print(answer % MOD)
Problem p02727 (python)

Fixed submission:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

X, Y, A, B, C = map(int, readline().split())
P = sorted(map(int, readline().split()), reverse=True)
Q = sorted(map(int, readline().split()), reverse=True)
R = sorted(map(int, readline().split()), reverse=True)

P = P[:X]
Q = Q[:Y]
nums = P + Q + R
nums.sort(reverse=True)
answer = sum(nums[:X + Y])
print(answer)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int, read().split())
AB = zip(m, m)

MOD = 10 ** 9 + 7

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

size_d = [0] * (N + 1)
dp_d = [1] * (N + 1)

for v in order[::-1]:
    dp_d[v] *= fact[size_d[v]]
    dp_d[v] %= MOD
    p = parent[v]
    s = size_d[v] + 1
    size_d[p] += s
    dp_d[p] *= fact_inv[s] * dp_d[v]
    dp_d[p] %= MOD

size_u = [N - 2 - x for x in size_d]
dp_u = [1] * (N + 1)

for v in order[1:]:
    p = parent[v]
    x = dp_d[p]
    x *= dp_u[p]
    x *= fact_inv[size_d[p]]
    x *= fact[size_d[v] + 1]
    x *= pow(dp_d[v], MOD - 2, MOD)
    x *= fact[size_u[v]]
    x *= fact_inv[size_u[p] + 1]
    dp_u[v] = x % MOD

for xd, xu, sd, su in zip(dp_d[1:], dp_u[1:], size_d[1:], size_u[1:]):
    su += 1
    x = xd * xu * fact[sd + su] * fact_inv[sd] * fact_inv[su] % MOD
    print(x)
Problem p02734 (python)

Fixed submission:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 998244353

N, S, *As = map(int, read().split())

U = 3010
answer = 0
f = np.zeros(U, np.int64)
for A in As:
    f[0] += 1
    f[A:] += f[:-A].copy()
    f %= MOD
    answer += f[S]

answer %= MOD
print(answer)

Buggy submission (verdict: Runtime Error):
from numpy import *
M=998244353
N,S,*A=map(int,open(0).read().split())
a=0
f = np.zeros(S+1, np.int64)
for b in As:
  f[0]+=1
  f[b:] += f[:-b].copy()
  f%=M
  a+=f[S]
print(a%M)
Problem p02747 (python)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = read().rstrip().decode()

def solve(S):
    N = len(S)
    if N % 2 == 1:
        return False
    T = 'hi' * (N//2)
    return S == T

print('Yes' if solve(S) else 'No')

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,read().split())

def solve(N,M):
    if N > M:
        return solve(M,N).T
    H = np.array([[0]], np.int8)
    for i in range(M):
        H = np.tile(H, (2,2))
        H[1<<i:,1<<i:] ^= 1
    H = np.diff(H, axis=0)
    H = np.diff(H, axis=1)
    return (H % 2)[:(1<<N) - 1]

H = solve(N,M)
rows = (''.join(map(str, row)) for row in H)
print('\n'.join(rows))
Problem p02761 (python)

Fixed submission:
import sys

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

N, M = map(int, readline().split())
if M == 0:
    print([0, 10, 100][N - 1])
    exit()
m = map(int, read().split())
S, C = zip(*zip(m, m))

def test(n):
    st = str(n)
    if len(st) != N:
        return False
    for i, c in zip(S, C):
        i -= 1
        if st[i] != str(c):
            return False
    return True

def main():
    for n in range(1000):
        if test(n):
            return n
    return -1

print(main())

Buggy submission (verdict: Runtime Error):
import sys

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

N, M = map(int, readline().split())
m = map(int, read().split())
S, C = zip(*zip(m, m))

def test(n):
    st = str(n)
    if len(st) != N:
        return False
    for i, c in zip(S, C):
        i -= 1
        if st[i] != str(c):
            return False
    return True

def main():
    for n in range(1000):
        if test(n):
            return n
    return -1

print(main())

Buggy submission (verdict: Runtime Error):
import sys

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

N, M = map(int, readline().split())
m = map(int, read().split())
S, C = zip(*zip(m, m))

def main(S, C):
    nums = [-1] * N
    for s, c in zip(S, C):
        s -= 1
        if nums[s] != -1 and nums[s] != c:
            return -1
        nums[s] = c
    if nums[0] == 0:
        return -1
    if nums[0] == -1:
        nums[0] = 1
    for i in range(1, N):
        if nums[i] == -1:
            nums[i] = 0
    return ''.join(map(str, nums))

print(main(S, C))
Problem p02764 (python)

Fixed submission:
import sys
from cmath import rect
import numpy as np
import numba
from numba import njit
i8 = numba.int64

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

eps = 1e-9

@njit((numba.complex128, numba.float64) * 2, cache=True)
def cross_circles(c1, r1, c2, r2):
    d = abs(c1 - c2)
    if d <= abs(r1 - r2) or r1 + r2 <= d:
        return None
    cos_theta = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)
    theta = np.arccos(cos_theta)
    z1 = (c2 - c1) * rect(r1 / d, theta)
    z2 = (c2 - c1) * rect(r1 / d, -theta)
    return (c1 + z1, c1 + z2)

@njit
def test(Z, C, t):
    R = t / C
    cand = list(Z)
    for j in range(len(Z)):
        for i in range(j):
            points = cross_circles(Z[i], R[i], Z[j], R[j])
            if points is not None:
                for p in points:
                    cand.append(p)
    cand = np.array(cand)
    cnt = np.zeros(len(cand), np.int64)
    for i in range(len(Z)):
        cnt += np.abs(cand - Z[i]) <= R[i] + eps
    return np.any(cnt >= K)

N, K = map(int, readline().split())
nums = np.array(read().split(), np.float64)

Z = nums[::3] + 1j * nums[1::3]
C = nums[2::3]

l = 0
r = 10**9
for _ in range(100):
    m = (l + r) / 2
    if test(Z, C, m):
        r = m
    else:
        l = m

print(r)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
from math import acos, cos, sin

# %%
N, K = map(int, readline().split())
m = map(int, read().split())
XYC = zip(m, m, m)
X, Y, C = zip(*XYC)
X = [complex(x, y) for x, y in zip(X, Y)]


# %%
def cross_pts(x1, r1, x2, r2):
    D = abs(x1 - x2)
    if r1 + r2 <= D:
        return
    if abs(r1 - r2) >= D:
        return
    theta = acos((r1 * r1 + D * D - r2 * r2) / (2 * r1 * D))
    z = complex(cos(theta), sin(theta)) * r1 / D
    yield x1 + (x2 - x1) * z
    yield x1 + (x2 - x1) * z.conjugate()


# %%
def test(cost):
    R = [cost / c for c in C]

    def gen_y():
        for i in range(N):
            yield X[i].imag - R[i]
            yield X[i].imag + R[i]
        for i, j in itertools.combinations(range(N), 2):
            for x in cross_pts(X[i], R[i], X[j], R[j]):
                yield x.imag
    Y = sorted(gen_y())
    for y1, y2 in zip(Y, Y[1:]):
        y = (y1 + y2) / 2
        event = []
        for i in range(N):
            if R[i] < abs(X[i].imag - y):
                continue
            dx = (R[i] ** 2 - (X[i].imag - y) ** 2) ** .5
            event.append((X[i].real - dx, 1))
            event.append((X[i].real + dx, -1))
        event.sort()
        n = 0
        best_n = 0
        for _, dn in event:
            n += dn
            if n > best_n:
                best_n = n
        if best_n >= K:
            return True
    return False


# %%
left = 0
right = 10 ** 7
for _ in range(100):
    x = (left + right) / 2
    if test(x):
        right = x
    else:
        left = x
print(right)