#---------- 入力例 ----------
# .が空間、#が爆弾
mp = '''........
..#...#.
........
....#...
.....#..'''
#----------------------------
print('【 元のマップ 】 ')
print(mp)
print()

# 入力データを二次元配列に設定
res = [list(line) for line in mp.split('\n')]

# 隣接８方向への相対位置を定義
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

for y, row in enumerate(res):           # 縦ループ
    for x, s in enumerate(row):         # 横ループ
        if s == '.':                    # 空きマスの場合
            res[y][x] = 0               # 初期化（周囲の爆弾数）
            for dx, dy in dxy:          # ８方向をループ
                x1, y1 = x + dx, y + dy # マスの周囲をx1,y1とする
                # マップ外の場合はパス
                if x1 < 0 or x1 > len(row) - 1 or y1 < 0 or y1 > len(res) - 1:
                    pass
                elif res[y1][x1] == '#':    # 周囲が爆弾'#'の場合
                    res[y][x] += 1          # 爆弾数カウントアップ

print('【 隣接する爆弾の個数を表示したマップ 】 ')
for row in res:
    print(*row, sep='')

#---------- 入力例 ----------
a = 2   # 500円玉の枚数
b = 2   # 100円玉の枚数
c = 2   # 50円玉の枚数
x = 100 # 目標金額
#----------------------------
res = 0     # 何通りあるかという解
# 全探索
for a1 in range(a + 1):          # 500円玉の枚数分ループ
    for b1 in range(b + 1):      # 100円玉の枚数分ループ
        for c1 in range(c + 1):  # 50円玉の枚数分ループ
            # 合計金額がＸ円に一致した場合
            if 500 * a1 + 100 * b1 + 50 * c1 == x:
                # それぞれの硬貨の枚数を出力
                print(f'500円{a1}枚、100円{b1}枚、50円{c1}枚')
                res += 1            # 解をカウントアップ
print('解：', res)

#---------- 入力例 ----------
cows = 'BBFBFBB'    # F:前向き、B:後ろ向き
#----------------------------
n = len(cows)   # 牛の頭数
k = 1           # 求める最小の牛を回転させる連続頭数（初期化）
m = n           # 求める最小の操作回数（初期化）

# 牛を回転させる連続頭数ｋを固定した時の最小操作回数を求める
# 解が存在しない場合は -1 を返す
def calc(k):
    # 区間[i, i + k - 1 ]を回転させたかどうか
    f = [0 for _ in range(n)]
    res = 0         # 操作回数
    total = 0       # リストfの和
    for i in range(n - k + 1):
        if (dir[i] + total) % 2 != 0:   # 先頭の牛が後ろを向いている場合
            # 回転操作を行う
            res += 1
            f[i] = 1
        total += f[i]
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    # 残りの牛が前を向いているかどうかチェック
    for i in range(n - k + 1, n):
        if (dir[i] + total) % 2 != 0:
            return -1
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    return res

# 牛の方向を0(F：前向き),1(B：後ろ向き)に変換
dir = [0 if x == 'F' else 1 for x in list(cows)]

for i in range(1, n + 1):   # 牛の頭数分ループする
    print(i, '頭回転させる機械の場合')
    x = calc(i)
    if x >= 0 and m > x:    # 牛を全部前向きにでき、かつ操作回数がより少ない場合
        print(x, '回操作で牛を全部前向きにできる。')
        m = x       # 最小の操作回数を更新
        k = i       # 回転させる最小の連続頭数を更新
    else:
        print('牛の向きを全部前向きにするとはできない。')
    print()

print(f'解：回転させる最小の連続頭数={k}　最小の操作回数={m}')

#---------- 入力例 ----------
# .が空間、#が壁
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)