#----- 入力例１ -----
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})')

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)

flow_value, flows = nx.maximum_flow(G, 's', 't')
print(f'maximum flow: {flow_value}')

caps = nx.get_edge_attributes(G, 'capacity')
for u in nx.topological_sort(G):
    for v, flow in sorted(flows[u].items()):
        print(f'  ({u}, {v}): {flow}/{caps[(u, v)]}')

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5

nx.draw_networkx(G)

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5])  # 1 → 2 → 3 → 4 → 5 → 1

nx.draw_networkx(G)

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5])  # 1 → 2, 1 → 3, 1 → 4, 1 → 5

nx.draw_networkx(G)

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node(5)            # 頂点を１つ削除
G.remove_nodes_from([3, 4]) # 頂点を複数削除

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)                
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)     
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

# # 辺の削除
G.remove_edge(3, 4)                   # 辺を１つ削除
G.remove_edges_from([(1, 3), (2, 5)]) # 辺を複数削除

import networkx as nx

G = nx.Graph()    # 無向グラフ

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

import networkx as nx

G = nx.DiGraph()  # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)