##Exercice 1

def produit(A,B):
    n = len(A)
    P = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                P[i][j] += A[i][k] * B[k][j]
    return P

def oriente(A): #le graphe est orienté ssi la matrice n'est pas symétrique
    n = len(A)
    for i in range(n):
        for j in range(i):
            if A[i][j] != A[j][i]:
                return True
    return False

def distance(A, i, j):
    n = len(A)
    if i == j:
        return 0
    C = A
    for i in range(1,n):
        if C[i][j] != 0:
            return i
        C = produit(A,C)
    return float('inf')

##Exercice 2

def binaire(k, n):
    L = [0]*n
    for i in range(n-1, -1, -1):
        L[i] = k%2
        k = k//2
    return L

#binaire(38, 8) = [0, 0, 1, 0, 0, 1, 1, 0]

#-38 a pour représentation en complément à deux :
#[1, 1, 0, 1, 1, 0, 1, 0]


##Exercice 3

def transpose(G):
    n = len(G)
    Gt = [[] for _ in range(n)]
    for u in range(n):
        for v in G[u]:
            Gt[v].append(u)
    return Gt

def attracteur(G, S, F):
    n = len(G)
    strat = [None for _ in range(n)]
    A = [False]*n
    ds = [len(L) for L in G]
    Gt = transpose(G)
    def parcours(v):
        if not A[v]:
            A[v] = True
            for u in Gt[v]:
                ds[u] -= 1
                if S[u]:
                    strat[u] = v
                    parcours(u)
                elif ds[u] == 0:
                    parcours(u)
    for v in range(n):
        if F[v]:
            parcours(v)
    return A, strat

##Exercice 4

# d(0,0) = G[0][0]
# Si i >= 1 et j >= 1 : d(i,j) = G[i][j] + min(d(i-1,j), d(i,j-1))
# Si i = 0, j >= 1    : d(0,j) = G[0][j] + d(0,j-1)
# Si j = 0, i >= 1    : d(i,0) = G[i][0] + d(i-1,0)


def cout_min(G):
    m = len(G)
    n = len(G[0])
    d = [[0] * n for _ in range(m)]
    d[0][0] = G[0][0]
    for j in range(1, n):
        d[0][j] = d[0][j-1] + G[0][j]
    for i in range(1, m):
        d[i][0] = d[i-1][0] + G[i][0]
    for i in range(1, m):
        for j in range(1, n):
            d[i][j] = G[i][j] + min(d[i-1][j], d[i][j-1])
    return d[m-1][n-1]

def cout_min_chemin(G):
    m = len(G)
    n = len(G[0])
    d = [[0] * n for _ in range(m)]
    d[0][0] = G[0][0]
    for j in range(1, n):
        d[0][j] = d[0][j-1] + G[0][j]
    for i in range(1, m):
        d[i][0] = d[i-1][0] + G[i][0]
    for i in range(1, m):
        for j in range(1, n):
            d[i][j] = G[i][j] + min(d[i-1][j], d[i][j-1])
    # Reconstruction du chemin
    chemin = [(m-1, n-1)]
    i, j = m-1, n-1
    while i > 0 or j > 0:
        if i == 0:
            j -= 1
        elif j == 0:
            i -= 1
        elif d[i-1][j] <= d[i][j-1]:
            i -= 1
        else:
            j -= 1
        chemin.append((i, j))
    chemin.reverse()
    return d[m-1][n-1], chemin