## Q1
'''
Le cadran indique les valeurs suivantes :

50, 82, 52, 90, 95, 55, 0, 99, 0

Il passe trois fois par 0, le code est donc bien 3.
'''

## 2
def mot_passe(L):
    somme = 50
    code = 0
    for elem in L :
        if elem[0] == 'R':
            signe = 1
        else :
            signe = - 1
        val = elem[1]
        somme = somme + signe*val
        somme = somme % 100
        if somme == 0 :
            code = code + 1
    return code
## 3
def croissant(L):
    return L[1] > L[0]


## 4
def rapport_correct(L):
    if croissant(L):
        signe = 1
    else :
        signe = -1
    for i in range(len(L)-1):
        if signe*(L[i+1] - L[i]) > 2:
            return False
    return True

## 5
def nb_corrects(L):
    compteur = 0
    for l in L :
        if rapport_correct(l):
            compteur = compteur + 1
    return compteur

## 6



def maximum(L):
    max = L[0]
    i_max = 0

    for i in range(1, len(L)):
        if L[i]>max :
            i_max = i
            max = L[i]

    return max, i_max

## 7


def tension_batterie(L):
    max, i_max = maximum(L)
    if i_max < len(L) - 1 :
        max2, i_max2 = maximum(L[i_max+1:])
        res = 10*max + max2
    else :
        max2, i_max2 = maximum(L[0:i_max])
        res = max + 10*max2
    return res

## 8

''' Il faut choisir 12 piles parmi donc le nombre de combinaisons
est le coefficient binomiale 12 parmi 100 soit 1050421051106700 combinaisons
Il n'est pas raisonnable de toutes les tester.
'''

## 9

if nb == 0 :
    res = 0


## 10
'''Si  n - i == nb alors le nombre de piles disponibles est égale au nombre de
piles à prendre. Il faut donc toutes les allumer ainsi : '''

elif n - i == nb:
    res = 0
    for j in range(i, n):
        res = res + ligne[j]*10**(-j+n-1)

## 11

'''Si la pile i est la première pile allumée de la série alors la tension
est la tension de cette * 10 ^(nb-1) + la tension maximale que l'on obtient avec les piles suivantes
Sinon, la pile i n'est pas allumée et la tension maxmimale est obtenue avec les piles
d'indice supérieur ou égal à i + 1

'''
## 12

D = {}
def rec():
    # Problème déjà résolu ?
    # Sinon cas de bases ?
    # Sinon appels récursifs
    # Mémoïsation dans D
    return res
## 13

D = {}
def U_max(i, nb):
    n = len(ligne)
    if (i, nb) in D :
        return D[i, nb]
    elif n - i == nb:
        res = 0
        for j in range(i, n):
            res = res + ligne[j]*10**(-j+n-1)
    elif nb == 0 :
            res = 0
    else :
        test1 = U_max(i+1, nb)
        test2 = ligne[i]*10**(nb-1) + U_max(i+1, nb-1)
        res = max(test1, test2)
    D[i, nb] = res
    return res

## 14

print(U_max(0, 12))

## 15

def uc_bottom_up(ligne, nb):
    n = len(ligne)
    D = {}
    for j in range(nb+1) :
        D[n-1, j] = 0
    for i in range(n) :
        D[i, 0] = 0
    for j in range(1, nb+1):
        for i in range(n-j, -1, -1) :
            if i == n-j :
                res = 0
                for k in range(i, n):
                    res = res + ligne[k]*10**(-k+n-1)
                D[i, j] =  res
                print(i, j, res)

            else :
                cas1 = D[i+1, j]
                cas2 = ligne[i]*10**(j-1) + D[(i+1, j-1)]
                res = max(cas1, cas2)
            D[i, j] = res
    return D
## 16

def solution(ligne, nb):
    D = uc_bottom_up(ligne, nb)
    i = 0
    val = D[0, nb]
    lst = []
    ligne = M[0]
    lst_val = []
    while nb > 0 and i < len(ligne)-1:
        if val == ligne[i]*10**(nb-1) + D[(i+1, nb-1)]:
            lst.append(i)
            nb = nb - 1
            lst_val.append(ligne[i])
        i = i + 1
        val = D[i, nb]
        if val == ligne[i]:
            lst.append(i)