import heapq

def astar(edges, nodes, goal):
    dist = [float('inf')] * len(nodes)
    dist[0] = 0
    q = []
    heapq. heappush( q, [0, [0]])
    
    while len(q) > 0:
        _, u = heapq.heappop(q)
        last = u[-1]
        if last == goal:
            return u
        for i in edges[last]:
            if dist[i[0]] > dist[last] + i[1]:
                dist[i[0]] = dist[last] + i[1]
                # 推定値を踏まえてコストを算出
                heapq.heappush(q, [dist[last] + i[1] + nodes[i[0]], u + [i[0]]])
    return []
    
# コストの推定値
nodes = [ 10, 14, 10, 10, 9, 9, 5, 0, 9, 8, 6, 4, 7, 3 ]

# 辺のリスト（終点とコストのリスト）
edges = [ [[4, 1], [5, 1]],
          [[2, 12], [3, 4], [4, 15]],
          [[1, 12], [9, 2], [11, 6]],
          [[1, 4], [5, 3], [8, 3]],
          [[1, 15], [0, 1], [6, 6]],
          [[0, 1], [3, 3], [6, 4]],
          [[4, 6], [5, 4], [10, 1]],
          [[11, 4], [13, 5]],
          [[3, 3], [9, 1], [10, 5]],
          [[2, 2], [8, 1], [12, 1]],
          [[6, 1], [8, 5], [13, 3]],
          [[2, 6], [7, 4], [12, 5]],
          [[9, 1], [11, 5], [13, 6]],
          [[7, 5], [10, 3], [12, 6]] ]

print('解：', astar( edges, nodes, 7))

goal = [0b111000000, 0b000111000, 0b000000111,  # 横に３つ並んだケース
        0b100100100, 0b010010010, 0b001001001,  # 縦に３つ並んだケース
        0b100010001, 0b001010100]               # 斜めに３つ並んでケース

# ３つが並んだか判定
def check(player):
    for mask in goal:
        if player & mask == mask:
            return True
    return False

# ミニマックス法
def minmax(p1, p2, turn):
    if check(p2):
        if turn:        # 自分の手番のときは勝ち
            return 1
        else:
            return -1   # 相手の手番のときは負け
    
    board = p1 | p2
    if board == 0b111111111:    # すべて置いたら引き分けで終了
        return 0
    
    w = [i for i in range(9) if (board & (1 << i)) == 0]

    if turn:    # 自分の手番の時は最小値を選ぶ
        return min([minmax(p2, p1 | (1 << i), not turn) for i in w])
    else:       # 相手の手番の時は最大値を選ぶ
        return max([minmax(p2, p1 | (1 << i), not turn) for i in w])

# 交互に置く
def play(p1, p2, turn):
    if check(p2):   # ３つ並んでいたら出力して終了
        print('勝負あり')
        print([bin(p1), bin(p2)])
        return

    board = p1 | p2
    if board == 0b111111111:    # すべて置いたら引き分けで終了
        print('引き分け')
        print([bin(p1), bin(p2)])
        return
    
    # 置ける場所を探す
    w = [i for i in range(9) if (board & (1 << i)) == 0]
    # 各場所に置いたときの評価値を調べる
    r = [minmax(p2, p1 | (1 << i), True) for i in w]
    print('選択可能なマス目', w)
    print('マス目の評価値', r)

    # 評価値が一番高いマス目を取得する
    j = w[r.index(max(r))]
    print('選択するマス目', j)
    print('----------------------------')
    play(p2, p1 | (1 << j), not turn) # 手番を入れ替えて次を探す

play(0, 0, True)      # プレイ開始

import random

goal = [0b111000000, 0b000111000, 0b000000111,  # 横に３つ並んだケース
        0b100100100, 0b010010010, 0b001001001,  # 縦に３つ並んだケース
        0b100010001, 0b001010100]               # 斜めに３つ並んでケース

# ３つが並んだか判定
def check(player):
    for mask in goal:
        if player & mask == mask:
            return True
    return False

# 交互に置く
def play(p1, p2):
    if check(p2):   # ３つ並んでいたら出力して終了
        print('勝負あり')
        print([bin(p1), bin(p2)])
        return

    board = p1 | p2
    if board == 0b111111111:    # すべて置いたら引き分けで終了
        print('引き分け')
        print([bin(p1), bin(p2)])
        return
    
    # 置ける場所（マス目）を探す
    w = [i for i in range(9) if (board & (1 << i)) == 0]
    # ランダムに置く
    r = random.choice(w)
    play(p2, p1 | (1 << r)) # 手番を入れ替えて次を探す

play(0, 0)      # プレイ開始

# 引数 n 円盤の残り枚数
# 引数 src 移動元
# 引数 dist 移動先
# 引数 via 経由場所
def hanoi(n, src, dist, via):
    global cnt
    cnt += 1
    if n > 1:
        # n - 1枚を移動元から経由場所に移す
        hanoi(n - 1, src, via, dist)
        print(src + ' -> ' + dist)
        # n -1枚を経由場所から移動先に移す
        hanoi(n - 1, via, dist, src)
    else:
        print(src + ' -> ' + dist)

n = int(input())    # 円盤の枚数（標準入力）

cnt = 0             # 移動回数
hanoi(n, 'a', 'b', 'c')
print('解（移動回数）：', cnt)

lst = [13, 7, 9, 11, 5, 7, 2, 4, 15, 6]

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2    # 半分の位置を算出
    # 再帰的に分割
    left = merge_sort(lst[:mid])   # 左側を分割
    right = merge_sort(lst[mid:])  # 右側を分割
    # 統合
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0

    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:         # 左 ≦ 右　の場合
            result.append(left[i])      # 左側から１つ取り出して追加
            i += 1
        else:
            result.append(right[i])     # 右側から１つ取り出して追加
            j += 1
    
    # 残りをまとめて追加
    if i < len(left):
        result.extend(left[i:])         # 左側の残りを追加
    if j < len(right):
        result.extend(right[j:])        # 右側の残りを追加
    return result

print('解：', merge_sort(lst))

# 近づける値
goal = 10000000
# 各都道府県の人口（北海道から沖縄まで）
pref = [ 5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039, 2916976,
        1974255, 1973115, 7266534, 6222666, 13515271, 9126214, 2304264, 1066328,
        1154008, 786740, 834930, 2098804, 2031903, 3700305, 7483128, 1815865,
        1412916, 2610353, 8839469, 5534800, 1364316, 963579, 573441, 694352,
        1921525, 2843990, 1404729, 755733, 976263, 1385262, 728276, 5101556,
        832832, 1377187, 1786170, 1166338, 1104069, 1648177, 1433566 ]

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):    # 人口データ探索終了
        return
    if total < goal:        # 枝狩り① 目標人口数を超えていない場合
        if abs(goal - (total + pref[pos])) < abs(goal - min_total): # 枝狩り② ズレが少ない場合
            min_total = total + pref[pos]                           # 合計値を更新
        search(total + pref[pos], pos + 1)      # 選ぶ場合（その都道府県の人口を足す）
        search(total, pos + 1)                  # 選ばない場合（その都道府県の人口を足さない）

search(0, 0)
print('解：', min_total)

x = 10
def calc(x):
    x += 20
    return x

print(x)
print(calc(x))
print(x)

a = [10]
def calc(a):
    a[0] += 20
    return a

print(a)
print(calc(a))
print(a)

a = [10]
def calc(a):
    a = [20]
    return a
     
print(a)
print(calc(a))
print(a)

data = '000000111111100111000000001111'

flg = 0
count = 0
result = []
for i in data:
    if int(i) == flg:
        count += 1
    else:
        result.append(count)
        count = 1
        flg = 1 - flg

result.append(count)
print(result)

#--------- 入力例1 ----------
n = 1       # ボールの個数
h = 10      # ボールの高さ（メートル）
r = 10      # 半径（メートル）
t = 100     # 経過時間（秒）
#--------- 入力例2 ----------
# n = 2       # ボールの個数
# h = 10      # ボールの高さ（メートル）
# r = 10      # 半径（メートル）
# t = 100     # 経過時間（秒）
#----------------------------
import math
g = 10.0    # 重加速度

# 時刻 T でのボールの位置
def calc(t):
    if t < 0:
        return h
    t1 = math.sqrt(2 * h / g)
    k = int(t / t1)
    if k % 2 == 0:
        d = t - k * t1
        return h - g * d * d / 2
    else:
        d = k * t1 + t1 - t
        return h - g * d * d / 2

# 各ボールごとの最終位置を算出する
lst = [calc(t - i) for i in range(n)]

for x in sorted(lst):
    print('{:.2f}'.format(x), end=' ')
print()

from queue import Queue
#--------- 入力例 -----------
s = ['.....#',
     '####..',
     '......',
     '#.####',
     '......']
#----------------------------
h = len(s)      # グリッドの高さ
w = len(s[0])   # グリッドの横幅

# マス(x,y)を表すペア
que = Queue()
# dist[x,y]は、マス(x,y)への最短経路長
dist = [[-1] * w for _ in range(h)]

# 幅優先探索の初期条件
que.put((0, 0))  # スタート位置
dist[0][0] = 0

# 幅優先探索
while que.empty() == False:
    # キューから要素を取り出す
    qx, qy = que.get()

    # 上下左右への移動を試す
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        x, y = qx + dx, qy + dy
        # 配列外の参照の場合
        if x < 0 or x >= h or y < 0 or y >= w:
            continue
        # 白マスの場合 かつ マス(x, y)が未探索の場合
        if s[x][y] == '.' and dist[x][y] < 0:
            # マス(x, y)をキューに追加して、最短経路長を更新
            que.put((x, y))
            dist[x][y] = dist[qx][qy] + 1

# 白マスの数をカウント
cnt_white = sum(line.count('.') for line in s)

print('解：', cnt_white - dist[h - 1][w - 1] - 1)