Aller au contenu

Longueur maximale d'un intervalle équilibré⚓︎

On considère une liste bits constituée uniquement de 0 et 1. Écrire une fonction telle que l_max_equilibree(bits) renvoie la longueur maximale d'une tranche qui contient autant de 0 que de 1.

Exemples

🐍 Console Python
>>> bits = [0, 0, 1, 0, 0, 0, 1, 1, 0, 0]
>>> l_max_equilibree(bits)
6
En effet, la tranche [1, 0, 0, 0, 1, 1] est équilibrée et de longueur maximale.

🐍 Console Python
>>> bits = [1, 1, 1, 1]
>>> l_max_equilibree(bits)
0
En effet, la tranche [] est équilibrée et de longueur maximale.

🐍 Console Python
>>> bits = [1, 0, 1, 0, 1]
>>> l_max_equilibree(bits)
4
En effet, la tranche [1, 0, 1, 0] est équilibrée et de longueur maximale. Il y a également [0, 1, 0, 1] équilibrée et aussi de longueur maximale.

⚠ On attend un algorithme qui fait une simple boucle. Il faudra sauvegarder une information utile à chaque tour de boucle.

###(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 : 10/10

.128013:pbv(40i2+edxm3;s7= 1o5w_lSnatf-)9h]6,qcrg.[yPku8/050m0l0E0D0i0A0r0u0O0A0D0r0r0t010E0i0c010406050r0W0o0o0D0P0T040B0w0A0W0?0w0C050Y0}0 11130{0c041c1j051m0Y1m1o1j0{0m0i0e0+0-0/0;0J0i0Q0J0A1C0J0E0_050$0d0A0l1x0.0:011B1D1F1D0E1L1N1J0E0d0w0m131K0P1k0E0J0+160r0c0D0C0;0j011P1z010F0(0l0C0D0o0l1J1;1?1{1R1~1N21230_0a0u0U0P0w0c0w0r0i190C0u0!1/0P0P0l0O2o1c260C1k0Y1-2B0E1+1*1,0m280;1F0C202l1J1u1w0,1Q2L0i2N0C1%1v1J0c2u1k2z2B2)0|1=2p2T1|2Y0P100A0_0u0v2y2-0`2,272/1R2;2?2^0j2{1?2}2z2K01320D2@040u0p362A0{39300;3c3e0u0g3i382-3a3o2^0x3s3k3u3m3b0w2=3d2^0L3z2~2.1y313E333f0s3J3l3M3n3O3G3f0X3S3B3U3D3F3p0I3!2 3$3w040v0h3+3L2U3%3P0v2`1d2|3A3,3@3.0v353|373~3?2:3W3e0v3h443j3K3v490_0v3r4d3t3 483(4i3y4l464g4p3/3I4s4f3C413R4y3T404h3/3Z4D3#4F4v0v3*4J4n3N4v0j3;4P474R3P0j3{2+1p2%1c2R2E0m2I3a0O1%241k4)1n4%4#2+4.0!2(4K1|0V0_0!0F3s4z3$0y2^534E2:0F0_0A0z100n0z0l0N0W0(0i0d2u0l584}1R0^040f5q4Q3n0_0d2n0r5w4W0;5t0H0b3z0u5K0u54400_0i0z1$0C0W0r0z4!2|5M591R0w0_0t3s5Z5r5F0_0S5D3a0o0i0_4U2+5!5,040K5J5L5N2:5P5R1a5U0z5@5Y5 5#5%5)685`5.4l6c015;5?5/3C5t5|4s5L5*5x3b5c5e0D0n6b5_015$045(4l6q5E6h5=0466456p6g0C500l0A0$6x5+6z6a6D6g6i6I5}5K6g4 040F3E6S6r6N040i6k3$5t0M6+6F6-6w6W6y0w566.1b6{6T0C0d0_200~0l0P0D0E5p6f6y5t5v7d725z5B6:3@5G5I6o6p5~6y6%0i52716,0_6`2)6E3a6A0t6C7A6X6H5X376g5t7o2)067q7Q7B4A6O6Q0D6@7C0_0k7F676y6Y7J3j7R7S3$6%6P0r7c5^6T7M6!7+7,5O040!7V7X3C6A0G7#377`1|7(7^6L7s5P7v7G6y6-7}6R7w6F6A020Q0E0q7 3-74042b7l1|7f8u31615S647)4|6r5G8p3@818G867I8x5`7N3}7_7r7i6.625T5V8C6g6A0R8M6s040D0c0c200m8#8w7h7x6.8-0_0H888R6r7.1F8c7$6T8I8/6^7U8h8d8 0_8l8n8J318r8t913a8.7=8:5Q8A5V6J2A7L8?9a0;90956r879e6l0_8O6K8Q858y8T9k658#8Z8#6-8(8*0C8,9w6;0_7g9h928;9P7m9p7p7Q6$758|9q8$8g7W8i7Y04980q832A9C0;6Y9m8D6F7@9Z7_9#6.8}846M5P9(9s8~9i8U8B8=046e9T3v939+ae9x5{a5978m8o9,7T8s6u7z2|9o049z7*9B898S5d5fal6B9(6-6/ap3$a6a28e8z638WabadauaN7|6P94aT7?0_6n7O7+9 7/7;aY8E9y9(0O0v0_032qaW0D0u026Q9:0u0hax0`az9 7uaGa4aJ8H0_0Gb49EaP9G9W8v5-9Hb89Jagaba#a78jam99b660araDbe5sa-9}b1aUaC6vaE9;3fa39V9tbo04b9br9D9jbc9_avaS7K6|bibv5yaV7~bW016m7^9 2u0E0W0P70bIafbtbC4y0Y4`0l2B2$b^4(1v4*2E2G2C1$1(2E0D1Mb{0Y4)0{c80#0%0)04.

###(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 : 10/10

.128013:pbv(40i2+edxm3;s7= 1o5w_lSnatf-)9h]6,qcrg.[yPku8/050m0l0E0D0i0A0r0u0O0A0D0r0r0t010E0i0c010406050r0W0o0o0D0P0T040B0w0A0W0?0w0C050Y0}0 11130{0c041c1j051m0Y1m1o1j0{0m0i0e0+0-0/0;0J0i0Q0J0A1C0J0E0_050$0d0A0l1x0.0:011B1D1F1D0E1L1N1J0E0d0w0m131K0P1k0E0J0+160r0c0D0C0;0j011P1z010F0(0l0C0D0o0l1J1;1?1{1R1~1N21230_0a0u0U0P0w0c0w0r0i190C0u0!1/0P0P0l0O2o1c260C1k0Y1-2B0E1+1*1,0m280;1F0C202l1J1u1w0,1Q2L0i2N0C1%1v1J0c2u1k2z2B2)0|1=2p2T1|2Y0P100A0_0u0v2y2-0`2,272/1R2;2?2^0j2{1?2}2z2K01320D2@040u0p362A0{39300;3c3e0u0g3i382-3a3o2^0x3s3k3u3m3b0w2=3d2^0L3z2~2.1y313E333f0s3J3l3M3n3O3G3f0X3S3B3U3D3F3p0I3!2 3$3w040v0h3+3L2U3%3P0v2`1d2|3A3,3@3.0v353|373~3?2:3W3e0v3h443j3K3v490_0v3r4d3t3 483(4i3y4l464g4p3/3I4s4f3C413R4y3T404h3/3Z4D3#4F4v0v3*4J4n3N4v0j3;4P474R3P0j3{2+1p2%1c2R2E0m2I3a0O1%241k4)1n4%4#2+4.0!2(4K1|0V0_0!0F3s4z3$0y2^534E2:0F0_0A0z100n0z0l0N0W0(0i0d2u0l584}1R0^040f5q4Q3n0_0d2n0r5w4W0;5t0H0b3z0u5K0u54400_0i0z1$0C0W0r0z4!2|5M591R0w0_0t3s5Z5r5F0_0S5D3a0o0i0_4U2+5!5,040K5J5L5N2:5P5R1a5U0z5@5Y5 5#5%5)685`5.4l6c015;5?5/3C5t5|4s5L5*5x3b5c5e0D0n6b5_015$045(4l6q5E6h5=0466456p6g0C500l0A0$6x5+6z6a6D6g6i6I5}5K6g4 040F3E6S6r6N040i6k3$5t0M6+6F6-6w6W6y0w566.1b6{6T0C0d0_200~0l0P0D0E5p6f6y5t5v7d725z5B6:3@5G5I6o6p5~6y6%0i52716,0_6`2)6E3a6A0t6C7A6X6H5X376g5t7o2)067q7Q7B4A6O6Q0D6@7C0_0k7F676y6Y7J3j7R7S3$6%6P0r7c5^6T7M6!7+7,5O040!7V7X3C6A0G7#377`1|7(7^6L7s5P7v7G6y6-7}6R7w6F6A020Q0E0q7 3-74042b7l1|7f8u31615S647)4|6r5G8p3@818G867I8x5`7N3}7_7r7i6.625T5V8C6g6A0R8M6s040D0c0c200m8#8w7h7x6.8-0_0H888R6r7.1F8c7$6T8I8/6^7U8h8d8 0_8l8n8J318r8t913a8.7=8:5Q8A5V6J2A7L8?9a0;90956r879e6l0_8O6K8Q858y8T9k658#8Z8#6-8(8*0C8,9w6;0_7g9h928;9P7m9p7p7Q6$758|9q8$8g7W8i7Y04980q832A9C0;6Y9m8D6F7@9Z7_9#6.8}846M5P9(9s8~9i8U8B8=046e9T3v939+ae9x5{a5978m8o9,7T8s6u7z2|9o049z7*9B898S5d5fal6B9(6-6/ap3$a6a28e8z638WabadauaN7|6P94aT7?0_6n7O7+9 7/7;aY8E9y9(0O0v0_032qaW0D0u026Q9:0u0hax0`az9 7uaGa4aJ8H0_0Gb49EaP9G9W8v5-9Hb89Jagaba#a78jam99b660araDbe5sa-9}b1aUaC6vaE9;3fa39V9tbo04b9br9D9jbc9_avaS7K6|bibv5yaV7~bW016m7^9 2u0E0W0P70bIafbtbC4y0Y4`0l2B2$b^4(1v4*2E2G2C1$1(2E0D1Mb{0Y4)0{c80#0%0)04.

Indice 1

On pourra calculer pour chaque indice la différence delta entre le nombre de 1 et le nombre de 0 depuis le début de la liste.

Lorsqu'on rencontre à nouveau une même valeur de delta, on déduit une tranche équilibrée.

Indice 2

On va alors stocker le premier indice où l'on rencontre delta. On pourra noter i_bonus_1[k] le premier indice où delta est égal à +k, et i_bonus_0[k] le premier indice où delta est égal à -k.

On pourra utiliser un dictionnaire i_bonus, ou deux listes i_bonus_1 et i_bonus_0.