依图笔试算法第二套笔试题， python，AC一三题

## 第一题直接模拟。。


def y1():
    n = int(sys.stdin.readline().strip())
    x = list(map(int, sys.stdin.readline().strip().split()))
    y = list(map(int, sys.stdin.readline().strip().split()))

    i, j = 0, 0
    ans = 0
    while i < len(x) and j < len(y):
        if y[j] >= x[i]:
            ans += (j - i) * x[i]
            y[j] -= x[i]
            x[i] = 0
            i += 1
        else:
            if y[j] > 0:
                ans += (j - i) * y[j]
                x[i] -= y[j]
                y[j] = 0
            j += 1
    print(ans)

## 第三题分组运算。。。

def y3():
    x = list(map(int, sys.stdin.readline().strip().split()))
    n, k = x[0], x[1]
    y = list(map(int, sys.stdin.readline().strip().split()))
    t1 = []
    t2 = []

    ans = 0
    for i, a in enumerate(y):
        if a % 3 == 0:
            ans += 1
        elif a % 3 == 1:
            t1.append(a)
        elif a % 3 == 2:
            t2.append(a)

    if len(t1) != 0 and len(t2) != 0:
        length = min(len(t1), len(t2))
        if k <= length:
            print(ans + k)
        elif k > length:
            les = max(len(t1), len(t2)) - length
            ans += length + min(les // 3, (k - length) // 2)
            print(ans)
        return

    length = max(len(t2) // 3, len(t1) // 3)
    print(ans + min(k // 2, length))

#### 第二题用floyd通过率为0。。。。

def y2():
    x = list(map(int, sys.stdin.readline().strip().split()))
    n, m, A, B = x[0], x[1], x[2], x[3]
    d = list(map(int, sys.stdin.readline().strip().split()))
    p = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    path = [[-1] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        x = list(map(int, sys.stdin.readline().strip().split()))
        a, b, t = x[0], x[1], x[2]
        p[a][b] = t

    c = [0]

    def dfs(i, j):
        k = path[i][j]
        if k == -1:
            return
        dfs(i, k)
        c[0] += d[k - 1]
        dfs(k, j)

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if p[i][j] >= p[i][k] + p[k][j]:
                    p[i][j] = p[i][k] + p[k][j]
                    path[i][j] = k

    dfs(A, B)
    ans = str(p[A][B]) + ' ' + str(c[0] + d[A - 1] + d[B - 1])
    print(ans)