cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/atcoder/arc/arc122_b_insurance_median.test.py

Depends on

Code

# verification-helper: PROBLEM https://atcoder.jp/contests/arc122/tasks/arc122_b

from fractions import Fraction
from decimal import Decimal, getcontext
from statistics import mean

def ftod(fraction):
    getcontext().prec = 50
    return Decimal(fraction.numerator) / Decimal(fraction.denominator)

def main():
    N, = read()
    A = read()
    x = Fraction(int(median(A)*2), 4)
    ans = x + mean(max(Fraction(0), a - 2*x) for a in A)
    write(f"{ftod(ans):.20f}")

from cp_library.math.median_fn import median
from cp_library.io.read_int_fn import read
from cp_library.io.write_fn import write

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://atcoder.jp/contests/arc122/tasks/arc122_b

from fractions import Fraction
from decimal import Decimal, getcontext
from statistics import mean

def ftod(fraction):
    getcontext().prec = 50
    return Decimal(fraction.numerator) / Decimal(fraction.denominator)

def main():
    N, = read()
    A = read()
    x = Fraction(int(median(A)*2), 4)
    ans = x + mean(max(Fraction(0), a - 2*x) for a in A)
    write(f"{ftod(ans):.20f}")

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def median(A):
    med = qselect(A, M := (N := len(A)) >> 1)
    return med if N&1 else (med + qselect(A, M-1)) >> 1


from random import randint

def partition(A, l, r, p) -> int:
    '''Partition subarray [l,r)'''
    A[p], A[r], p = A[r := r-1], A[p], l
    for j in range(l, r):
        if A[j] <= A[r]: A[p], A[j], p = A[j], A[p], p+1
    A[p], A[r] = A[r], A[p]
    return p

def qselect(A, k, l=0, r=None):
    '''Find kth element in subarray [l,r)'''
    if r is None: r = len(A)
    while l != r-1:
        if k < (p := partition(A, l, r, randint(l,r-1))): r = p
        elif k > p: l = p+1
        else: return A[k]
    return A[k]


def read(shift=0, base=10):
    return [int(s, base) + shift for s in input().split()]
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == '__main__':
    main()
Back to top page