#---------- 入力例 ----------
# .が空間、#が壁
mp = '''...#....#.
...#....#.
...#....#.
######..#.
...#....#.
...#.....#
...#.....#
##########
...#.....#
...#.....#'''
#----------------------------

mp_compress = {}  # 縦と横を圧縮したデータ

print(' 【 圧縮前 】 ')
print(mp)
print()

# 縦を圧縮
lst = []    # 縦を圧縮したデータ
pre = ''    # １行前のデータ（初期化）
for line in mp.split():
    if pre != line:
        lst.append(line)
    pre = line
# 横を圧縮
pre = ''  # １列前のデータ（初期化）
w = 0
for col in range(len(lst[0])):  # 列ごとにループ
    row = [l[col] for l in lst] # 1列分のデータを取得
    line = ''.join(row)
    if pre != line:
        for y, s in enumerate(list(line)):
            mp_compress[w, y] = s
        w += 1
    pre = line

print(' 【 圧縮後 】 ')
for y in range(len(lst)):
    for x in range(w):
        print(mp_compress[x,y], end='')
    print()

# 深さ優先探索(Depth-First Search)
def dfs(x, y):
    global mp_compress
    # 今いるところを#に置き換え
    mp_compress[x, y] = '#'
    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
        pos = (x + dx, y + dy)
        if pos in mp_compress and mp_compress[pos] == '.':
            dfs(pos[0], pos[1])
# 領域を数える
cnt = 0
for pos,v in mp_compress.items():
    if v == '.':
        dfs(pos[0], pos[1])
        cnt += 1
print('解：', cnt)

#------ 入力例 ------
k = 2           # 選択する個数
# それぞれの品物の重さと価値
items = [{'weight':2, 'value':2},
         {'weight':5, 'value':3},
         {'weight':2, 'value':1}]
#--------------------
# 重さあたりの価値[x]が実現可能かどうか
def check(x):
    # それぞれの品物に対して、（価値 - 重さあたりの価値[x] × 重さ）を計算する
    res = [item['value'] - x * item['weight'] for item in items]
    res = sorted(res, reverse=True) # 大きいほうからソート
    return sum(res[:k]) >= 0  # 大きいほうからｋ個の和が０以上かどうか

# 解の存在範囲を初期化
lb, ub = 0, 999
for _ in range(100):      # 十分な回数繰り返す
    mid = (lb + ub) / 2   # 解の存在範囲の中央値
    if check(mid):        # 中央値が実現可能かどうか
        lb = mid
    else:
        ub = mid
print('解：', lb)

#------ 入力例 ------
m = 3       # 馬の頭数
lst = [1, 2, 8, 4, 9]   # 小屋の位置
#--------------------
n = len(lst)    # 小屋の数

# 条件を満たす距離かどうかを判定
def check(d):
    last = 0              # 小屋の位置①
    for _ in range(m - 1):# 最初の馬は１番目の小屋に入れるので（馬の頭数 - １頭）分ループする
        crt = last + 1    # 小屋の位置②
        # 小屋の位置が存在し かつ
        # 小屋の位置①と小屋の位置②がある距離[d]未満だったら
        while crt < n and lst[crt] - lst[last] < d:
            crt += 1      # 小屋の位置２を後ろにずらす（距離[d]を確保するため）
        if crt == n:      # 最後の小屋の位置をこえたら
            return False  # 条件を満たさない
        last = crt        # 条件を満たしたので、小屋の位置①を小屋の位置②に移動
    return True           # すべての馬を小屋にいれられたので条件を満たす

lst = sorted(lst)   # 小屋の位置を昇順にソート

# 解の存在範囲を初期化
lb = 0
ub = 9999
# 条件を満たすかどうか解の存在範囲を狭めながらチェックする
while ub - lb > 1:
    mid = (lb + ub) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid
print('解：', lb)

#------ 入力例 ------
lst = [8.12, 7.53, 4.47, 5.29]  # 各紐のながさ
k = 11           # 作りたい同じ長さの紐の本数
#--------------------
n = len(lst)    # 紐の本数

# 長さｘの紐をｋ本作れるかどうか
def check(x):
    cnt = sum([int(l / x) for l in lst])
    return cnt >= k

lb = 0         # 初期化（下限の範囲）
ub = 999999    # 初期化（上限の範囲）

# 解の存在範囲が十分狭くなるまで繰り返す
for _ in range(99):
    mid = (lb + ub) / 2
    if check(mid):
        lb = mid
    else:
        ub = mid

# 小数点第２までを切り捨て
print(('解: {:.2f}').format(lb * 100 // 100))

#----- 入力例１ -----
lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
k = 5
#----- 入力例２ -----
# lst = [-10,4,6,100,200,400,500]
# k = 10
#----- 入力例３ -----
# lst = range(99999999999)
# k = 30000
#--------------------
n = len(lst)

# 解の存在範囲を初期化
lb = -1   # 下限の範囲
ub = n    # 上限の範囲

while ub - lb > 1:
    mid = (lb + ub) // 2
    if lst[mid] >= k:
        ub = mid
    else:
        lb = mid
print('解', ub)