Aller au contenu

Algorithmes de tri⚓︎

On souhaite trier une liste L, c'est-à-dire réarranger ses éléments pour qu'ils soient rangés dans l'ordre croissant. Par exemple, si L = [5, 1, -4, 2, -8, 7] alors un algorithme de tri doit permettre d'obtenir la liste [-8, -4, 1, 2, 5, 7]. Dans ce TP, nous étudions plusieurs algorithmes de tri. Pensez à bien tester toutes vos fonctions.

Tri par sélection⚓︎

Le tri par sélection consiste à chercher le minimum que l'on met en 1ère position de la liste, puis le 2ème plus petit élément en 2ème position...

Exercice⚓︎

Écrire une fonction minimum(L, i) qui renvoie l'indice du minimum de la liste L à partir de la position i. Par exemple, si L = [5, 1, -8, 2, -4, 7], minimum(L, 0) doit renvoyer 2 (correspondant à L[2] = -8) et minimum([5, 1, -8, 2, -4, 7], 3) doit renvoyer 4 (correspondant à L[4] = -4).

Exercice⚓︎

Écrire une fonction tri_selection(L) qui trie une liste L en utilisant le tri par sélection. On pourra compléter le code suivant :

Python
1
2
3
4
def tri_selection(L):
    for i in range(len(L)):
        m = minimum(L, i)
        # Ă©changer L[i] et L[m]

Tri par insertion⚓︎

Le tri par insertion consiste à trier progressivement la liste L, de gauche à droite. Plus précisément, à l'étape i, les i premiers de L sont triés et on fait en sorte d'insérer le i+1ème élément L[i] au bon endroit pour que les i+1 premiers éléments soient triés.

Voici les étapes du tri par insertion pour la liste L = [5, 1, -4, 2, -8, 7] : - i = 0 : on insère L[0] = 5 de façon à ce que le 1er élément de L soit trié (il n'y a rien à faire : un élément seul est toujours trié). L vaut [5, 1, -4, 2, -8, 7] (on met en gras la partie de L déjà triée). - i = 1 : on insère L[1] = 1 au bon endroit, ce qui donne [1, 5, -4, 2, -8, 7] - i = 2 : on insère L[2] = -4 au bon endroit, ce qui donne [-4, 1, 5, 2, -8, 7] - i = 3 : on insère L[3] = 2 au bon endroit, ce qui donne [-4, 1, 2, 5, -8, 7] - i = 4 : on insère L[4] = -8 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7] - i = 5 : on insère L[5] = 7 au bon endroit, ce qui donne [-8, -4, 1, 2, 5, 7]

On a terminé, et la liste est bien triée.

Exercice tri insertion⚓︎

Complète le code de la fonction tri_selection

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oP;f 8lkg5:j,bry2a1éh3tvw=u6e[(Sàn9]_s-c)7iqçm/4p0d050Z0D0x0s0R0h0M0f0O0h0s0M0M0A010x0R0X010406050M0B0U0U0s0p0q040G0b0h0B0@0b0I050V0~1012140|0X04051k1d1n0V1k0|0Z0R0y0,0.0:0=0.0I0j0B0s0j0D0N0X0q0x0v1b0f0v0R0j0v0h1P0v0x0`050%0o0h0D1w0/0;011O1Q1S1Q0x1Y1!1W0x0p1l1K0,170M0X0s0I0=0r011$1y010e0)0D0I0s0U0D1W1{1}221(251!282a0`0a0f0c0p0b0X0b0M0R1a0I0f0#1_0p0p0D0O2v1d2d0I1l0V1K2I1=1@1?1X0Z2f1z0R0I272s1W1t1v0-1%2S2U0I0b2Y1W0X2B1l2G2I2/0}1|2w2!232(0p110h1W0s1N2B0e0=030L0L0O2)0D1S2%0b0N0t3d0`0f0t1d0s2:2?0{2=2e2^1(2`2|2~300D32013436383a2V3d0N20040f0r3j3l1}3n2G2R013s0s2}1l2 0v313335370#3C2(3E0w3g0w3K2F3m0|3O3q0=3R3T053V3X3y3Z3B2T3D3e0W3g0W3,1e3.3o2@1x3r0b2{3S3u3W3w3Y3A3#3~3%3e0k3g0k442/3/2?3P3?4e3`3z3!394k3c3e0C3g0C4q463:493=4b3t3U3v3x4y3}3b3E0Q3g0Q4H3M4s3p4K3Q4M4d4O4f4Q3|4j4T3e0g3g0g4Y2H4!482#4%4c3@3_4g3{4i4A4/0N0J3g0J4@3N4t3;4|4N3^4P4h4z3$4C3d0Y0`0t0Y594_4u4(4~5g515i4B3E0t0t5n3i0V3k3-4Z475s4}4w504R4.3 3d3G0t3J5E3L4^5I5c4v4*4x4-535P0t3)045)5q5X4$5Z5f4+5h4S5(415+435U5G5W4J4{5:4 4,525j5z4n5+4p5|455H5 2_5t5L635x540t4E5+4G6a4r5.606f5!5M5$653e0t4V5+4X6o3m1o2-1d2Y2L0Z1@2Q5c4z2X1u1l2,0D2.6D6b2H054z6T2e0R0Z0=352G5z3u6#6%645y6x212j0D6-6i5(1W5|6d1(0i0`0#0e5}6Z4`230z3g726q2_0e0`1=0R0L2T0M0D0p2E6V733P0_040F786|3=0`0h7r5b4$7o0l720f793r0o7u0R0M0x7w4#4{7o0P7A7l0|7l5I6,016(2?3E3G5f7U6v6/3F6;296?7V6.547Z6{7x4{763H0f7^7K741(0M0Z0`0180727R2;3O7#0L6)3e5*7!6$7,6^4l0N3)0f6=6@5@8f8a7:7L237}3g7^0f0U2)0R251#0h004b0Z2B2x0D0+0u0h0u2a0I0x0+2y0h0f2r0B0p0f0S0B8z2 1S7I1#0M0b2u0f7d0u0D827`0f86880N5_8b8k5O8f418i7*8_5%8{6`5F7s018r7@7^80018.7S858c7W1}3E678^8d8l5k4n8}2a8 6w0N9i5U836D9d6-8=6l9j7$544E9o7+9C5P9A5U8t7C940I7c0(0h1!7B7D0=0b0`0A9T9N7F042i8/5c7o7q9c7;2_7u9(7y0`0P9b844t8;7X3e6z9B7-5P4V9F9q7%9}9K8t9U010O5B04030f0o0b0B0-1#8W0R0f0j2p0:8)0.8R120@1#8+1#0H2x2p2u0D0n0f0s0B2x0u0o190f0B2w7h0B8Q8I8K277J7Q8/9`9g4:6+9e9 8f4;a29k8`5k4;2I3k9La86~040e4b9Z9-3r0`0Ra_8p1(0b7?2Ta~7{3=9#0p1}1F9:7M0`9+9^a 0=0U0R5nbb237o0nbla{040%0)9S9,bg017N7P6pbv2waX0I3E564O868e5k56a)9H8fbG3K9v3M7Ta#8=5oa!a36j5mbMa$5kbWa.979L9Ma`7t040mb43P9W049Y7lb,bw9O04a}b_a8aa0`ad0maH0O0paS8M1#271_10270T1}0xas8Uar0y3S0D8T8F0f8A2T1t0O1#8P00aR8Lchay7g0u2B0p9@9w9_bU9{3dab9~bJ5z5Bb#cO6xcM9uaWcJaY5QbXa*90b%20cR9l5z7/a/b+7_94c1ac0Z0u0O3S1Ecv8z0E0R0K0f0y7i0+ar0jaF0O0v1#0m0B0M8W00ay0M2 0X0.cuaD1|8U0X7i0U190s2v0f0~0Ocuapd10+0sd10Odu1McyaTcpd5ahd8cGbS9x7,bV8a2 bIc*6x8h8jc#9r5)92b*a:94a=0z1Obu2/b`b53Q0`b:b 94b?020j0x0db;5cbi0`5pd?b-01b10`1}0Zd}5/9/bB7n0`0Ebpb.d=d-a8b?0Ne94{d 5+egbx0`0Ken23d^d`d|e2b{ebbfd/7oefec5Yd;er7o0Kbz46ecbD5z8@dSa#cS3d8|dXbNb%8@a6c.d%e3b|7veH9;04eGeD4ueJeAd/elev1(ep5De:9)etboe?e;9$eKeeerb|eicHbweLe_9V9Xfcd:f3e,bce.f6e=e}e-0Kf0ej9NeCf9eEf5fi9.b/ffe^f1d~bjeqfx1(fbaVePcXbE6x9ieTbY5(9neYb$66d#e%b+a8f7fA0`0Nb^fre3e{dM6WdO9ffM3d9AfPdY7%6k7)9pf@6j9J3kbRf-cI9ycK6yc!eZ5za1fTeVg5b)e(bwc;ad1|8O1#2B0x8T0IaDar8!0xca7I8u8w258,cicq2 a@0I2D0R1bf,2I6Y6E6S6G6P1d0x6JgO2O2J0s1ZgL0V6H7R0#bs0*04.

Exercice tri de 3 valeurs source codex⚓︎

Le tri du drapeau hollandais en bref

On l'utilise dans le cadre des tableaux ne contenant que trois valeurs distinctes (petite, moyenne et grande).

Il a pour avantage d'être de coût linéaire et de trier le tableau en un seul passage.

On partage le tableau en quatre zones :

  • les petites valeurs,
  • puis les valeurs moyennes,
  • puis les valeurs pas encore triĂ©es,
  • enfin les grandes valeurs.

Schéma

Schéma

L'algorithme s'arrĂŞte lorsque la zone des valeurs Ă  trier est vide.

On souhaite trier un tableau ne contenant que trois valeurs a, b et c répétées un nombre quelconque de fois. On souhaite trier ce tableau afin de placer au début les a suivis des b et enfin des c.

Par exemple, avec nombres = [2, 0, 2, 1, 2, 1] on a a = 0, b = 1 et c = 2. Le tableau trié est [0, 1, 1, 2, 2, 2].

Dans ce cas de figure, on peut utiliser le tri du drapeau hollandais.

Remarque

Ce tri a été inventé par Edsger Dijkstra qui était de nationalité néelandaise.

Il a donné son nom à l'algorithme en référence aux trois couleurs du drapeau néerlandais : Rouge, Blanc, Bleu.

Drapeau hollandais

L'idée est de maintenir quatre zones dans le tableau :

  • la première ne contient que des a,
  • la deuxième que des b,
  • la troisième des valeurs pas encore triĂ©es,
  • enfin la dernière zone ne contient que des c.

Ces zones sont délimitées par les bornes suivantes (toutes incluses):

  1. de l'indice 0 Ă  prochain_a - 1,
  2. de prochain_a Ă  actuel,
  3. de actuel + 1 Ă  prochain_c,
  4. de prochain_c + 1 Ă  len(tableau) - 1

Les quatre zones Les quatre zones

L'algorithme fonctionne ainsi :

  • Les variables prochain_a et actuel sont initialisĂ©es Ă  0,

  • La variable prochain_c est initialisĂ©e Ă  len(tableau) - 1,

  • On rĂ©pète les actions suivantes tant que la zone des valeurs restant Ă  trier est non vide :

    • On lit l'Ă©lĂ©ment Ă  l'indice actuel :

      • Si c'est un a, on le rajoute Ă  la fin de la zone des a en Ă©changeant les Ă©lĂ©ments d'indices prochain_a et actuel (Ă©tape 3 sur les figures),
      • Si c'est un b, on la laisse Ă  sa position (Ă©tape 2 et 6),
      • Si c'est un c, on la place Ă  la position prĂ©cĂ©dant le dĂ©but de la zone des c en Ă©changeant les Ă©lĂ©ments d'indices prochain_c et actuel (Ă©tape 1, 4 et 5),
      • Dans tous les cas, on prend soin de mettre Ă  jour les diffĂ©rents indices afin de reflĂ©ter les nouvelles Ă©tendues des zones.

Les figures ci-dessous illustrent le tri du tableau [2, 0, 2, 1, 2, 1] :

  • Étape 1

    Étape 1 Étape 1

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.⚓︎

    • Étape 2

    Étape 2 Étape 2

    On lit un 1 : on le laisse Ă  cette position.

    actuel est incrémenté.

  • Étape 3

    Étape 3 Étape 3

    On lit un 0 : on le place Ă  la fin de la zone des a.

    prochain_a et actuel sont incrémentés.

  • Étape 4

    Étape 4 Étape 4

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.

  • Étape 5

    Étape 5 Étape 5

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.

  • Étape 6

    Étape 6 Étape 6

    On lit un 1 : on le laisse Ă  cette position.

  • Étape 7

    Étape 7 Étape 7

    actuel est strictement supérieur à prochain_c.

    L'algorithme se termine.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oèPf8gbr1ûa3tv=uàn9xsc)7qR/p0dI; lk5:j+,y2éChw6e[(ES]_iHêm.4D-050E0W0n0l0%0I0v0H0w0I0l0v0v0p010n0%0C010406050v0q0*0*0l0i0P040!0b0I0q120b0s0H020l0*0C0G0H0A0W1c0i0z0q0W0v050B191b1d1f170C04051K1D1N0B1K170E0%0o0`0|0~100|0s0g0q0l0g0W0.0C0P0n0T1m0H0T0%0g0T0I1?0T0n15050=0h0I0W1W0}0 011=1@1_1@0n1 211}0n0i1L1.0`1i0v0C0l0s100Q01231Y010e0@0W0s1q0W1}2l2n2s252v212y0*2A040a0H0d0i0b0C0b0v0%1l1n0:2j0i0i0W0w2V1D2C0s1L0B1.2+2f2h2g1~0E2E1Z0%0s2x2S1}1T1V0{242^2`0s0b2~1}0C2!1L2)2+3b182m1n302t340i1c0I1}0l1;2!0e10030$0$0w350W1_330b0.0Q0.0j150H0j1D0l3c3f163e2D3h253j3l3n3p0W3r013t3v3x3z2{3C3C3G0Q3J3L2n3N2)2@013S0l3m1L3o0T3q3s3u3w0:3$343(0m3G0m3,2(3M173:3Q103?3^053`3|3Y3~3#2_3%3D0,3G0,471E493O3g1X3R0b3k3@3U3{3W3}3!404m423D0K3G0K4s3b4a3f3;4e4C4i3Z3 3y4I3B3D0V3G0V4O4u4b4x4d4z3T3_3V3X4W4l3A3(0y3G0y4)3.4Q3P4,3=4.4B4:4D4=4k4H4^3D0f3G0f4}2*4 4w31524A4f4h4E4j4G4Y5a0.0t3G0t5f3/4R4c5k4/4g4;4F4X414!3E0D150j0D5x5h4S535m5E5p5G4Z3(0j3F045Y5O4v5Q5l4U5o4?594n3E2q5!3+0B3K484~5%5A4T554V585r5.0j445!465?3-5g5`515|5D565F4@614p5!4r665^684+5j6b5n575q5H5X4L5!4N6k4t3.1O391D2~2.0E2h2?5A4X2}1U1L380W3a3M6l1L4X6Q2D0%0E103u2)5X3U6X6Z6s5W3D3F0H2I0W6)5V5s5Z476n2t0J150:0e6S695j0U3G6 6_3R0e152f0%0$0m0$0o3@0W0q0i1C6z2*702t14040Y745z6a15340*0h2!7j3d75107o0x0L6S177k6V1n6(016!3f3(5:5D7L5 6t3D2q6.2z6;6f4J3)2+3K0H7)0H7m3R15380b0w0T0?0s0$0l6S7+7B010b150p7`7,100*0%155N7I7H7A4R7S0$6#3D637R6Y7M6*5s447X2J7Z5-7#8g667*7{7s6o150l2$1A0I817|7~04807I8v505j84867G7r6W8i7N2n3(6h8h8p607#4p8n6:8j6=5.8V8t7*823=7.2P7;7?3v8D8w2t8F8H3b8J5i3i0h152H8P8~257o7q7I8-0s7u0b7w7y933;7D8@8K8_150.9i9483855!8O983:8c8e0.6v8W8%7!5I4L8#8X7U9x1}66896R9u8R8d7O4#6%9N8(7#4$9E9A8q5I4$7%048u8-6{040U1=219n4S8y8A3y9.5A8F020I0n0G8{3M8}9/047/8;2_8?9t8^95157F889f9v9P0.4`4:8c9T5I4`9W7T6+af9I7(8u8,7|9)0%6~8I999b9d1B9f5A7o0XaD7t048z0n8BaH5j7o0#9?518`9}3.9 5A8M04878a9ja804aa4Pac9N9w5cah9S9B3(5cam8k5.a.3,asa|aWaI7v7xaCa6a$7C15aGb39o8.aJ9;8Cb89g150#0OaR8x04b09ebeaEb6aN3i8/7:7=a47_bo51aPbj9k8GbB7-bl9cb17z9La7b504b7a#b99aa18:bv7@bxbPbf04bhbE4daAbIbra%bObKb4baaKaMbyaObg9sbXad8T3D5ua/9Fao5ua@aj3(b|a{a}9%7|bRa2bU7^b#7}150NaU2*a~8L9q3Iabbeb_0s5X5Kb}9X8Y5I5M2r6/b~6?csc5c67)azbbaL9=ay8Ecfch9$8-aYcma*coa,ae5Y9RcA616-czcu9GcW9#c69(154Yax8|cGbmb2bXbpbNb)b$cHb:c?bzb?cKbLce8GcNcj2tcQc_017oa)4ucT6)9w0j7Q3oaia;6,7Wc#an6?7Q8+cEd5bFb/cJc/cL04cgcdd7cnb^cUb`3E8gdia:9Y5X8mdna^7#62aq9$a}c+043y0v0Wd8dab@b,7KdFcq6,8VdJcYdQ8!dOc2d+dSdscFc8b%bnc}b=c^b;bsc{dwd%bYb!d0b-bRc;bJ6A7|aFd8c9bT8=0wd!c dxd18`cde9bHd|e4c@b+ecd1egbueiekbZbie7bQd{c=etc~d d}e1dvbdeLa%aQdDe4cp6ucXc$ao0j9Dd;dk3E9ydrcEcGcaeAeE3;8F0.d4cPcld$6A0B6U6B6P6D6M1D0n6Gf02;2,0l20e}0B6E1J7J3;2!0*0$0e0l0J0W0$0T631v1x1z1B0Hdbe_1R1M040F0I0H0v001(2U0H0E0q0H7/200c2JfFfEfG7+1w040-0i0l0C0W0lfH0(1i1!0E0?7jfR0H2_0o2x0n0RfI1d0H0Z0+0H0-0%0M0J0v2f0lf^1O3N1K0S22790H3o2R7hg87e0s0=1)fF000)2f222X3w0k0n0H3z0R0?2!0H0;fFg60i0%0W0igqg6f621fYgv1n0q1ndY0qfz2m0~1(0W0+g2fbg5fW0sf%gefA1:1k0@0%0v0l2Vgvf~gq0%84f/220rgx0_2cfX0q0u2j1r2S0R0_2X2f0bg)0H7e217hh2g)120s2$1BgT1Q3Nf90;0?0^04.

Tri fusion (récursif)⚓︎

Le tri fusion sur une liste L consiste à : - Séparer L en deux listes L1 et L2 de même taille. - Trier récursivement L1 et L2 pour obtenir des listes triées L1' et L2' - Fusionner L1' et L2' pour avoir un tri de L.

Le tri fusion est donc récursif.

Voici une illustration des Ă©tapes avec la liste [23, 12, 4, 56, 35, 32, 42, 57, 3] :

Pour commencer, on souhaite écrire le code de la fonction fusion qui prend en paramètres deux listes d'entiers liste_a, liste_b triées par ordre croissant et les fusionne en une seule liste triée liste_triee qu'elle renvoie.

Exemples
Python
1
2
>>> fusion([1, 6, 10], [0, 7, 8, 9])
[0, 1, 6, 7, 8, 9, 10]
Python
1
2
>>> fusion([1, 6, 10], [])
[1, 6, 10]
Python
1
2
>>> fusion([], [0, 7, 8, 9])
[0, 7, 8, 9]
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein Ă©cran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.128013oP;f 8lkg5:+,bry2a1h3tvw=u6e[(Sn9]_s-c)7im./4p0d050W0C0w0s0P0h0K0f0M0h0s0K0K0z010w0P0U010406050K0A0Q0Q0s0p0q040F0b0h0A0;0b0G050S0{0}0 110_0U04051h1a1k0S1h0_0W0P0x0)0+0-0/0+0G0j0A0s0j0C0L0U0q0w0u180f0u0P0j0u0h1M0u0w0@050!0o0h0C1t0,0.011L1N1P1N0w1V1X1T0w0p1i1H0)140K0U0s0G0/0r011Z1v010e0$0C0G0s0Q0C1T1^1`1 1#221X25270@0a0f0c0p0b0U0b0K0P170G0f0Y1?0p0p0C0M2s1a2a0G1i0S1H2F1/1;1:1U0W2c1w0P0G242p1T1q1s0*1!2P2R0G0b2V1T0U2y1i2D2F2,0`1_2t2X202#0p0~0h1T0s1K2y0e0/030J0J0M2$0C1P2!0b0L0B0L0t0@0f0t1a0s2-2:0^2/2b2=1#2@2_2{2}0C2 01313335372S3a0L1}040f0r3h3j1`3l2D2O013q0s2`1i2|0u2~3032340Y3A2#3C0v3e0v3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0T3e0T3*1b3,3m2;1u3p0b2^3Q3s3U3u3W3y3Z3|3#3b0k3e0k422,3-2:3N3;4c3^3x3Y364i393b0B3e0B4o443.473:493r3S3t3v4w3{383C0O3e0O4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0g3e0g4W2E4Y462Y4#4a3=3@4e3_4g4y4-0L0H3e0H4=3L4r3/4`4L3?4N4f4x3!4A3c0V0@0t0V574@4s4$4|5e4 5g4z3C0t3d045y5o455q4{4u4~4P4,3}3c3E0t3H0S3i3+4X5D5a4t4(4v4+515K0t3%5A3)5P3J4?5T4!5V5d4)5f4Q5!3 5A415)5R5+4H4_5.4}4*505h5x4l5A4n5`435S5}2?5r5G615v520t4C5A4E684p5,5~6d5W5H5Y633b0t4T5A4V6m4G595-6q5/5X625w6v4/5A4;6A6a6C6p5F6r6f5=4j3c545A566N5|6P6c6R6F6s6H520r5k046-571l2*1a2V2I0W1;2N5a4x2U1r1i2)0C2+3k5{1i4x742b0P0W0/322D5x3s7b7d6+5!1~2g0C7j6g7l2F5Q6b1#0i0@0Y0e766o200y3e7A7u3:0e0@0e0A2q187F6$1#0?040E7O4Z5~0@1P0K0w0C0J0s7U4^207R0n760f7B3p7X0P7Z7#0o7(3N7R0N0l760_692E5D7i017e2:3C3E5d836t6I3D7m267o847k6V885)0f8m7.7G3O0@0!0$1X7$7-7/0/0b0@0z8w8p0G0o7X247_5a7R7T80797)7:047Y7!8v8M8x017{7~7_8a0J7f3b5$897c8h7q6V3%0f7n7p6U5i8(8l8n8V0G8r0#0h8u7^8M8o7P8y8A8C933O8F8Q8H8U8p8K8I5-7;7?0J902.9d0@0N8Y9c4r8!8$0L5@8)8;5J6V3 8/8f9x5Z9z1T8^8m8`9h8S1/0P0C0C967V208z048B918V7R0D0I9p9l9r8*851`3C659w8+8=9+8e279D6u0L9,9H929R8P0P8T2,9{8O949U9Qa2010Q0P0@5n8M7 9$7a9(8#864B7hag8,5i4C9B9=9.9yan9G3i8na14s0@9~9k3kax5a9T9Va08Va8aa9#753M9sai0L6x9-8b524Tap8gaT5KaR9`8V7w040y1L1Xa57`0@8Laea68{049~7%9W8p9T020h0w0da,5U8|8t7#a^a:a-049oa_970b7D041`0Wb04!9e9q9|3:az9jbh4_a{a}a babl8q048s8~7@9f4_7{7}ac8Zag9t6KaS8i5i4/aW9?8cbJ9`awa$az7zbua;9Kb4bB7*0@0Db#9}9 aM977R9!bX3Nbra~bp2?bZbobka69Yb)bma?b`b68J0@0IbE6nb{0faO9*3b6XbKam3C54bOar9E5icdbSaw8_8Db_9M9Ob~019T0Rcua=0s0U0U24bgc8c37Scyb_b5b,bvb}cF9gc0cK3K9Xc4b9c7b6ca0G5x6.ce9/6v5kciaY6V5mau3Fcoc:9JcQb@1#9T0maGaCaIa95AaLcSaNbHaP5yakbP6h3dc*bL5x5z3Ic:9I8pa%360K9PcObC0@c644c8cY5x882|8!cf6v1}dadx5Lc.dfcoc=8R7#csdlc24!cwcIbecBcDcubjdL7W8Q7=8SaBd1b-b%dOaAdScUd081d27j9t5#d6cj9@d:dAc%3c8@avdEcp97a=d(b:aE0@c`c@0/aJc bFdrd3cb3c9vdvald_0t9A8:d=8cejdDd~bva%a)23e6bwa@evb=btaHcqbx8}8ucRd,d#04dp5Sebd.d49,egd75!4ld^as64epc;eCdH0JdJcudNdmb^dPcC0GcEdUb$cHe)8Pe!eG8Nb7b(e=b exe|8Wd*eacXeccZ6v6jc$eVf69;aXdbfa7sc/eYd bne^aDdMe4c{3Kfl4_e83gf2cL2tds6vaReQem6haVelc+5i6weXfq20esa*dKc|eCe1eBbb0@a|b?e2cPby8 d)eJd+e_fx3cbJfAfF5xbNfEfdf)fIbTeZdXdI0p9NfNd!bve(e/8PcAe,e.fvb7a/g5b1dW9idZeHcMd$e e0c1g8bif1cWg5f(0tcdf+f:gpfbeRc,cmd|fhbvghgc3F8Vc_fo2EfJ1#fsf$82f487c#grdB6-gufB5KgSfff?97a%2y0w0A0p19fWdVe!e$fucS0S786=736@701a0w6`g_2L2G0s1Wg?0S6^7 0Yby0K04.