med.py

#!/usr/bin/env python3

import random

#################################################
#  globals
#
#################################################

arr0 = []
arr1 = []
n = 0

#################################################
#  logic
#   (main())
#################################################

def main(): # C-style Python-programming :D
    global arr0, arr1, n
    #init("data.in") # file input
    init() # keyboard input
    ans = solve()
    print(ans)
    #print(" ".join(map(str,arr0)))
    #print(" ".join(map(str,arr1)))
    return

#################################################

def init(file = None): # initing globals
    global arr0, arr1, n        
    
    def takeArr(s):
        arr = s.split()
        arr = list(map(float, arr))
        return arr
    def isSorted(arr):
        return all(
            arr[i] <= arr[i+1] 
            for i in range(len(arr)-1)
        )
    
    if file is None:
        arr0 = takeArr(input())
        arr1 = takeArr(input())
    else:
        f = open(file, "r")
        arr0 = takeArr(f.readline().strip())
        arr1 = takeArr(f.readline().strip())
        f.close()
    
    n = len(arr0)
    if len(arr1) != n:
        raise ValueError(
"Me needs two sorted arrays of the **same size**"
        )
    if not(isSorted(arr0) and isSorted(arr1)):
        raise ValueError(
"Me needs two **sorted** arrays of the same size"
        )
    return

def solve_brute_way(): # O(n*log(n))
    global arr0, arr1, n
    arr = arr0 + arr1
    arr.sort()
#     len(arr) % 2 == 0 
#      always true, because 
#      len(arr) == 2 * n
    return (arr[n-1] + arr[n]) / 2

def solve_O_n(): # O(n)
    global arr0, arr1, n
    i = i0 = i1 = 0
    v0 = v1 = None
# like merge-function in merging sort
    while i <= n:
        v0 = v1
        if i0 != n  and (i1 == n or arr0[i0] <= arr1[i1]):
            v1 = arr0[i0]
            i0 += 1
        else:
            v1 = arr1[i1]
            i1 += 1
        i  += 1
    return (v0 + v1) / 2

def solve():
    global arr0, arr1, n
    #if n <= 50:
    #    return solve_brute_way()
    #else:
    return solve_O_n()

#################################################
#  some testing stuff 
#   (run_tests())
#################################################

def run_tests():
    profiles = ["no intersection"
                , "inclusion"
                , "intersection"
                , "same distribution"]
    count = 1000
    def check():
        b = solve_brute_way()
        s = solve_O_n() 
        return b == s
    def run_tests(profile, count):
        results = [init_test(profile, random.randint(600,1600)) 
                   and check() 
                   for _ in range(count)]
        
        return results
    def count_hits(results):
        results = filter(lambda x:x, results)
        results = list(results)
        return len(results)
    for profile in profiles:
        sch = run_tests(profile, count)
        sch = count_hits(sch)
        s  = "Profile: " + str(profile) + "\n"
        s += "  Count: " + str(count) + "\n"
        s += "Success: " + str(100 * (1 - sch / count)) + "%\n"
        print(s)

def init_rand(l, a0 = 0, b0 = 99
              , a1 = None, b1 = None): 
    global arr0, arr1, n
    if a1 is None:
        a1 = a0
    if b1 is None:
        b1 = b0
    
    n = l
    def takeRandArr(l, a, b):
        arr = [
            #random.random()
            random.randint(a,b)
            for _ in range(l) 
        ]
        arr.sort()
        return arr
    arr0 = takeRandArr(l, a0, b0)
    arr1 = takeRandArr(l, a1, b1)
    return

def init_test(i, l = random.randint(6,16)):
    global arr0, arr1, n
    n = l
    coin_tails = random.random() > 0.5
    if i == 0 or i == "no intersection":
        if coin_tails:
            init_rand(n, 0, 20, 100, 120)
        else:
            init_rand(n, 100, 120, 0, 20)
    elif i == 1 or i == "inclusion":
        init_rand(n, -20, 20)
        if coin_tails:
            arr0 = [x*2 for x in arr0]
        else:
            arr1 = [x*2 for x in arr0]
    elif i == 2 or i == "intersection":
        if coin_tails:
            init_rand(n, 0, 20, 10, 30)
        else:
            init_rand(n, 10, 30, 0, 20)
    else: # same distribution
        init_rand(n)
        
#################################################

#run_tests()
main()

#################################################
#  (example) 
#   data.in
#################################################
# 0.0295352153364562 0.037738769734166344 0.08236269858055989 0.09379663070374322 0.12094422034464702 0.13291900146059443 0.15069403686159166 0.158137851013037 0.18771930275575954 0.20560791979164172 0.21738352915016468 0.3119019682129427 0.34755824579011263 0.38256926566224403 0.3888911126999911 0.41009784024109963 0.4797199773745219 0.5635786716370051 0.5642726395504967 0.5775296315513274 0.6025282714584975 0.7168311868198883 0.7463431160211368 0.7592923890840861 0.8431183590504937 0.8651719119250607 0.9219947568546539 0.9395478113311354 0.9532673239895981 0.9817050270165614
# 0.11442494857900087 0.13584662907140954 0.1420899477184585 0.15599231487109166 0.157154302379932 0.15801950024266997 0.18724681022209055 0.21158548455124715 0.22987804412689117 0.2913380352006518 0.297686193263789 0.3118391853888065 0.378879751699975 0.43310717657765074 0.4453404647668069 0.4494128519676691 0.457893756651482 0.4919949833308297 0.5901224960165474 0.6545925406274127 0.7193440159448474 0.8249635562995055 0.8734872097449103 0.9057237851160254 0.9244835135216061 0.9257452468163365 0.9282402073415297 0.9372102600996493 0.9473293092222195 0.9840384744388788
#################################################
# answer: 0.4392238206722288
#################################################