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

import networkx as nx

G = nx.DiGraph()

# 始点ノード、終了ノード、重さ(weight)を定義
G.add_weighted_edges_from(
    [('A', 'B', 4), ('A', 'C', 3), ('B', 'C', 1), ('B', 'D', 1), ('B', 'E', 5), 
     ('C', 'F', 2), ('D', 'E', 3), ('F', 'E', 1), ('E', 'G', 2), ('F', 'G', 4), ]
)

# ノードの位置（グラフ描画用） => ノード名:(横位置, 縦位置)
pos = {'A': (0, 1), 'B': (1, 2), 'C': (1, 0), 'D': (2, 1), 'E': (3, 2),
       'F': (3, 0), 'G': (4, 1)}

edge_labels = {}
for (i, j) in G.edges():
    edge_labels[i, j] = f"{ G[i][j]['weight'] }"

nx.draw(G, pos=pos, with_labels=True, node_size=500)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

# ダイクストラ法で最短経路とその重み（最小コスト）を求める
start, end = "A", "G"
shortest_path = nx.dijkstra_path(G, start, end)
shortest_path_weight = nx.dijkstra_path_length(G, start, end)

# 出力
print("Shortest Path:", shortest_path)
print("Weight:", shortest_path_weight)

import networkx as nx

G = nx.DiGraph()

#(始点，終点，重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
                  ('s', '2', dict(capacity=2)),
                  ('1', '2', dict(capacity=6)),
                  ('1', '3', dict(capacity=6)),
                  ('3', '2', dict(capacity=3)),
                  ('2', 't', dict(capacity=5)),
                  ('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

cut_value, partition = nx.minimum_cut(G, 's', 't')
print(f'cut value: {cut_value}')

S, T = partition
print(f'  (S, T): ({S}, {T})')