<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 2A.algo - Puzzles algorithmes (1) - correction
Eléments de réponses pour des puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, produits scalaires, problèmes de recouvrements, soudoyer les prisonniers, découpage stratifié.
Step1:  Produits scalaires
Le problème est tiré de Google Jam 2008, round 1A.
On considère deux tableaux $v=(v_1,..., v_n)$ et $w=(w_1,...,w_n)$. On souhaite le minimum 
Step2:  Seconde solution
Ce programme améliore la solution précédente.
Step3:  Vous pouvez observer le déroulement de ces deux solutions sur PythonTutor.
Soudoyer les prisonniers
Problem C. Bribe the Prisoners
Approche par programmation dynamique
Une observation fondamentale à faire pour ce problème est la suivante. Imaginons qu'un oracle nous donne le nombre de pièces
d'or minimum à dépenser pour toutes les prisons contenant strictement moins de $P$ cellules et strictement moins de $Q$ prisonniers. On peut alors r´esoudre notre problème par 
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Explanation: 2A.algo - Puzzles algorithmes (1) - correction
Eléments de réponses pour des puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, produits scalaires, problèmes de recouvrements, soudoyer les prisonniers, découpage stratifié.
End of explanation
def recouvrement(B, intervalles) :
    # initialisation
    entier = {}
    pred   = {}
    for a,b in intervalles:
        if 0 <= a <= B :
            for k in range(0,b+1):
                entier[k] = 1
                pred [k] = (a,b)
    
    # programmation dynamique
    i = 0
    while i <= B:
        mini = None
        best = None 
        for a,b in intervalles:
            if a <= i <= b:
                a = max(0,a)
                for l in range(a, b+1):
                    if l in entier:
                        d = entier[l] + 1
                        if mini is None or d < mini:
                            mini = d
                            best = (a,b)
        entier[i] = d
        pred[i] = best
        i += 1
        
    # on retourne la solution
    if B in entier:
        sol = []
        while B > 0:
            p = pred[B]
            m = max(0,p[0])
            sol.append ( p )
            B = p[0]
        sol.reverse()
        return sol
    else:
        # la solution n'existe pas
        return None
        
b = 1
intervalles = [ (-1, 0), (0,1), (0,0) ]
print("sol=",recouvrement(b, intervalles))
Explanation: Produits scalaires
Le problème est tiré de Google Jam 2008, round 1A.
On considère deux tableaux $v=(v_1,..., v_n)$ et $w=(w_1,...,w_n)$. On souhaite le minimum : $\min_{\sigma,\sigma'} \sum_{i=1}^{n} v_{\sigma(i)} w_{\sigma'(i)}$ où $\sigma,\sigma'$ sont deux permutations de l'ensemble $[[1,...,n]]$.
Problème de recouvrement
Première solution
Elle est inspiré de la distance d'édition. Si on doit recouvrir l'ensemble des entiers $[[0,n]]$, on passe en revue tous les intervalles qui inclut 0. On construit deux tableaux :
$entier[i]$ : conserve le nombre minimum d'intervalles pour couvrir tous les entiers de $0$ à $i$
$pred[i]$ : conserver le dernier intervalle utilisé pour recouvrir $i$
On commence par initialiser $entier[0]$ en passant en revue tous les intervalles qui inclut 0. Pour trouver $entier[i+1]$, on passe en revue tous les intervalles $[a,b]$, et on affirme que:
$entier[n+1] = \min { entier[a] + 1 \; si \; a \leqslant n+1 \leqslant b }$
Le tableau $pred[n+1]$ conserve l'intervalle qui minimise le problème de minimisation précédent.
Une fois les tableaux $entier$ et $pred$ renseigné, on utilise le tableaux $pred$ pour retrouver la solution.
End of explanation
from IPython.core.display import Image
Image("inter.png", width=500)
# solution par Benjamin DONNOT
def solve(B, intervalles):
    res = []
    upper = 0
    while True:
        aux = []
        for x in intervalles :
            if x[0] <= upper:
                aux.append ( x )
                
        new_intervalles = []
        for x in intervalles :
            new_intervalles.append ( x )
        intervalles = new_intervalles 
        
        if (aux ==[]) :
            return '0\n'
        
        mymax = max(aux,key=lambda x: x[1])
        res.append(mymax)
        upper = mymax[1]
        if(upper >= B):
            break
            
    return res
b = 1
intervalles = [ (-1, 0), (0,1), (0,0) ]
print("sol=",solve(b, intervalles))
Explanation: Seconde solution
Ce programme améliore la solution précédente.
End of explanation
from IPython.core.display import Image
Image("priso.png", width=450)
Explanation: Vous pouvez observer le déroulement de ces deux solutions sur PythonTutor.
Soudoyer les prisonniers
Problem C. Bribe the Prisoners
Approche par programmation dynamique
Une observation fondamentale à faire pour ce problème est la suivante. Imaginons qu'un oracle nous donne le nombre de pièces
d'or minimum à dépenser pour toutes les prisons contenant strictement moins de $P$ cellules et strictement moins de $Q$ prisonniers. On peut alors r´esoudre notre problème par :
$$\min_{q \in Q} \left[ G(1,q-1) + G(q+1, P) + P - 1 \right]$$
On va donc utiliser cette observation pour calculer la quantité cherchée récursivement. D'autre part, afin d'éviter de refaire les
calculs plusieurs fois, on va mémoriser les réponses.
End of explanation
<END_TASK>