##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')

# SELECT id
# FROM CLIENTS
# WHERE ville = "Toulouse"
#
# SELECT email
# FROM CLIENTS
# JOIN PARTENAIRES
# ON CLIENTS.id = id_client
# WHERE partenaire = "SCEI"
#
# SELECT ville, COUNT(*)
# FROM CLIENTS
# GROUP BY ville


##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]

#43 = 2*16 + 11, 2 = 0*16 + 2
#11 s'écrit B en hexadécimal
#43 s'écrit donc 2B

##Exercice 3

def appartient(L, x):
    for y in L:
        if x==y:
            return True
    return False

#Pire cas : O(n), meilleur cas : O(1)

def minimum(L):
    m = L[0]
    for i in range(1, len(L)):
        if L[i] < min:
            m = L[i]
    return m

#Pire cas comme meilleur cas : O(n)

def recherche_dicho(L, x):
    g = 0
    d = len(L) - 1
    while g <= d:
        m = (g+d)//2
        if x == L[m]:
            return True
        elif x < L[m]:
            d = m-1
        else:
            g = m+1
    return False

#Meilleur cas : O(1), pire cas : O(log n)

def repartition(L):
    L1 = []
    L2 = []
    L3 = []
    p = L[0]
    for x in L:
        if x < p:
            L1.append(x)
        elif x == p:
            L2.append(x)
        else:
            L3.append(x)
    return L1, L2, L3

def tri_rapide(L):
    if len(L) <= 1:
        return L
    L1, L2, L3 = repartition(L)
    return tri_rapide(L1) + L2 + tri_rapide(L3)

#Meilleur cas : O(n log n), pire cas : O(n**2)

def parcours_profondeur(G):
    n = len(G)
    marque = [False]*n
    R = []
    def visiter(u):
        marque[u] = True
        R.append(u)
        for v in G[u]:
            if not marque[v]:
                visiter(v)
    return R

#Complexité en O(n + m), où n est le nombre de sommets et m le nombre d'arcs

##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