#--------- 入力例 ----------
n = 3           # 品物の数
a = [1, 2, 3]   # 各品物の個数
m = 3           # 分割数
#---------------------------
memo = {}

# １つも選ばない方法は常に一通り
for i in range(n + 1):
    memo[i, 0] = 1

for i in range(n):              # 品物の数に対応するループ
    for j in range(1, m + 1):   # 分割数に対応するループ
        if j - i -a[i] >= 0:
            memo[i + 1, j] = memo.get((i + 1, j - 1), 0) + memo.get((i, j), 0) - memo.get((i, j - 1 - a[i]), 0)
        else:
            memo[i + 1, j] = memo.get((i + 1, j - 1), 0) + memo.get((i, j), 0)

print('解：', memo[m, n])

#--------- 入力例 -----------
n = 4   # 品物の数
m = 3   # 分割数
#----------------------------
memo = {(0,0): 1}

for i in range(1, m + 1):       # 分割数に対応するループ
    for j in range(n + 1):      # 品物の数に対応するループ
        if j - i >= 0:
            memo[i, j] = memo.get((i - 1, j), 0) + memo.get((i, j - i), 0)
        else:
            memo[i, j] = memo[i - 1, j]
print('解：', memo[m, n])

def calc(s):
    stack = []
    for i in s.split(' '):
        # スタックの内容を表示
        print(stack)
        if i == '+':
            # +の時はスタックから数字を２つ取り出して加算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a + b)
        elif i == '-':
            # -の時はスタックから数字を２つ取り出して減算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a - b)
        elif i == '*':
            # *の時はスタックから数字を２つ取り出して乗算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a * b)
        elif i == '/':
            # /の時はスタックから数字を２つ取り出して減算し、結果をスタックに格納する
            b, a = stack.pop(), stack.pop()
            stack.append(a // b)
        else:
            # 演算子以外（数字）のときはその値を格納する
            stack.append(int(i))
    return stack[0]

print('解：', calc('4 8 2 + * 3 1 - 4 * -'))

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)