Apparier des rollers

Le professeur d'EPS est mécontent. Après une séance de rollers avec ses élèves, il constate que ceux-ci ont abandonné leurs patins dans le désordre dans le vestiaire.

Il est donc face à un grand tas de rollers dans lequel les paires sont toutes mélangées... Pire : il manque peut-être certains patins !

Vous devez donc l'aider à vérifier que chaque patin pourra trouver une « âme sœur ».

Pour chaque roller, il connait deux informations : son genre ("gauche" ou "droit") et sa pointure (un entier entre 36 et 46 inclus l'un et l'autre).

Une paire valide est composée d'un patin gauche et d'un droit, l'un et autre ayant la même pointure.

Les rollers sont donnés sous forme d'une liste dans laquelle chaque élément est un tuple (genre, pointure). Par exemple [("gauche", 40), ("gauche", 41), ("droit", 40)]. Cette liste ne permet pas d'apparier tous les patins : le patin ("gauche", 41) n'a pas de patin associé.

Écrire la fonction est_tas_valide qui prend en argument une liste décrivant les rollers et renvoie True ou False selon que chaque patin peut être apparié ou non.

Contrainte

Il est possible de résoudre ce problème en n'accédant qu'une unique fois aux caractéristiques de chaque patin.

Les tests supplémentaires vérifieront donc que, lors du traitement d'une liste de $N$ rollers, l'algorithme utilisé n'accède pas plus de $2 \times N$ fois à la liste.

Tri

Il est possible de résoudre cet exercice sans trier les patins ou leurs pointures. De plus pour de grandes listes de rollers, les tris sont longs à mettre en œuvre. Les fonctions de tri de Python (sorted et list.sort) sont donc interdites.

Exemples

>>> est_tas_valide([])
True
>>> est_tas_valide([("gauche", 40), ("droit", 40)])
True
>>> est_tas_valide([("gauche", 40), ("gauche", 41), ("droit", 40)])
False

Évaluations restantes : 10/10

.128013:p(40ed3;N 1E}o5_ên)h]6,qc[y!FCu»và8i2+DxmÀsU7=«ûwlSIatf-9O{Rrg.TéPkbè/050h0g0%0$0L0Z0S0l0A0Z0$0S0S0V010%0L0c010406050S0G0Q0Q0$0.0C040!0p0Z0G1b0p0t0l020$0Q0c0j0l0-0g1l0.0z0G0g0S050`1i1k1m1o1g0c041M1T051W0`1W1Y1T1g0h0L0I131517190v0L0/0v0Z1:0v0%1e050~0^0Z0g1+1618011/1;1?1;0%1|1~1`0%0^0p0h1o1{0.1U0%0v131r0S0c0$0t190M01201-010(100g0t1z0g1`2o2q2v222y1~2B0Q2D040a0l0?0.0p0c0p0S0L1u1w0|2m0.0.0g0A2Y1M2F0t1U0`2k2.0%2i2h2j0h2H191?0t2A2V1`1(1*14212{0L2}0t2e1)1`0c2%1U2,2.3f1h2p1w332w380.1l0Z1e0l0m2+3j1f3i2G3l223n3p3r0M3u2q3w2,2`013B0$3q040l0i3F2-1g3I3z193L3N0l0e3R3H3j3J3X3r0q3#3T3%3V3K0p3o3M3r0x3,3x3k1,3A3;3C3O0U3_3U3|3W3~3?3O0K423.443:3=3Y0*4a3y4c3)040m0f4h3{344d3 0m3t1N3v3-4i4q4k0m3E4v3G1V3d1M312;0h2^3J0A2e2N0{1)1U3c0g3e3v3#054N0|4V4y2w0@1e0|0(4X434q0Y3r4,4b4z0(1e1K0%0r0~0S0r0I3M0L0|4;4$221d040d534p3m1e2S0Z1~0.1L4D2-3`3J560u0b3,0l5q0l5k3/0t1e2p0L2%5h3f5s4-2w0p1e0V3#5C4=2w560B593J0Q0L1e4n5i3O5t4c4(040(3;5I5W4z5w0p360%0G2%5$5D220p4/04365/5K3A0^5c2q0/0g5O3/56585U5%2w5Q1e0i3^655:19560y5_541968040e416c5`6e1e0u0w5p5r66225Y5!0.6h5a3A1e5 0t5.6o6i016f6B3(5)5+5-605U5J6J5=1e5^6S6w3W5c1r5f5A4W6d6K1e5o5U065r6:6T6C195Y0L4+6Y6*5v046F6H5B6Z015F040V5H6{6p010S2t04010/0$0G0A0v2D614c566-3f6/6;7r726}5x5z7l4q5M7x5b042U6P703v6=3J740)6M3/6k6a7A551e6t786U1e0N77716*6k4u7p7r5q725Y0g116R3h6*7n6u7%6v6|5w0 7w6I6?6+045N7{6N7C5*0t5,7F3G7H3/7J7L4c7N6b7.79567S7Y797J7X7G727!3,7q7(6*6y5#7T7|6}4 1~5-8b4q6V5@0t8C7B7v1K7P6q047o4w7=7)6W6`8j6J8y3M0g8B8w7I1e0D8m878o5R045T8f6J7:6.7=6:8R042%858G8!3/0@0A1e0E3M0S7-8P7?795Y8_5-8{8U7|8~1e0;0.1J3_0`4Z4U4F9m0`4I1M0%4K9r2?2/2d2f2;0$1}9o4I1S4#7|2%0Q0r0(0$0@0g0r0v0i1e1E1G1I1K0l8O4E1Z3w1T0T2}0l4T5Q0_2%0l0$0c3c0p7i1 4N0t2W0S0%1 0J9W1V3w0G0Z3w1?040S0=2p2%0.0l1~122p1b9^0l930Z1vab8Yaa6 1 0d7f7h7j0l0p0G0l0h2S2X0u0l0j1Ma41ga42=0L0gaa7i0$0A0G9%0|120|0G0Pab0L9`9V0p0^9{0t1J12aD0`aF05a40S00216Qaa9UalaS8YaV1?aY121v0%ab0$0l0Q0s2Mab1v0/1J5-0:0l0O2q121~13162m840.7_1 ak0c8Yb01(2%2)1F2Ab02%0t0I0p0CaK5s9l04917,1MbGaCaE0La3bO4N1A1mbEac0l0=0Z0=2M84a_130v0$a@a|9{axbfab003;ay9?az172qb00bah0La^bWbYb!0%b$b4b6361(0A1 0hb.aMb*aXb,0tb:849(bj15b3b51 7D846Q0l10129%bq0G0Ibxcj120s2=1 9.a80L0=120}b10l5!0t2)0Lbpbr0lbzbBbDaa4Y4ObH926RbG0:bN3w0`a13w313J241=1@1_9F3J2J2A2C1e2P0!0A0.1cb00?0C2k1v4X4T9F3g4WbG8@4*8L015?5s805u4@044_4{164~5052dj7m1e648.8x6#5eaK6(4E7/6r9X3S8?7@6~7g9=dC2-884c748(dO7t5|a53;9{0hdf637 dx81cp85948)8t1e6z8H7Q57df6}aod!1e6g8|4j6Ocq865jdE040ud:198E6X9c815d6%e5016^8T8ndJd^d|8D5GdS5V6*7b1e7edL7j01d_040we48;968V4)azc2eddRed0tdV0SdX0gdZdt7ydvd$6)797u83d*ed8u6Aek5Ldvd?6E2Ae0c@62d`eId~eXePe$e3eG5?e8eheUdzece#6x8Se/6~e*d+dT6*dRendP4qeq7day5*1_ewey8qdI97f1e 3WdV2KewdweTeCdKas8Ke=d;eze9898$f9dU1efqfy8MfsdDe|04fe2XdNe,due3dG1f8Qd-8^0}9aeY8 c!bJ6.8rfa4%d.8vfBd}5@e^6W9be{8VdVbm0t5 frd?fp2Af~fI3K6Eetfxd%e-e35n7;6;8@6_f2ardMeweSfLfu0LfheGfDf2fOeFg37zg36}gngu7RfUf*fWflfY8`f#90c#fjeB9d5cfZ0.f@d,97f$9g9i6.bKcZ9n2.9D1X040F0}b,cF2S9=9(0.cIbx1 0t0=2q0Q83bg00369@0I0=0taJci2!aIbU9VaTa{ce1Kbcg(281 0=0~bq0l4_2m0X9{0G93hj1w380Q0^9,0hb:0c0=bm2YcJb0cwb0cC9,0=0I2X0=0gc(9Z9E0+1w1t10aXc91v0A9-1tb_ax9?0p1Ahn5g0l1Ig|0Z0l0C9-h#9(eW6QaS6_0(hzg;hCb/bp1m4N5-b00Z002A93htbhaRcT6$dBbc0?avaLb(aO0t0yahh-hj9`axawaobFcZesfwev9kcZimakg}g/c11 bhbR0ch)h=0Sb2d)6Qim2W381wakcl0h0=c bZg;hc1 cNcP1v2}c1cT1Ki89B0l069}i5hSa|0$2Yax00aPco2z9Wau1w1F0ci bVebdB0l0W0lghat0HiB2Za7j59Vjags0l0HhN1$g$0n1w2y2Zcoi1ih0Sjf0l9{aYcLa%5ehKh=cc1J0l8zamh=cY4!8J5hc%0l0!b}i?aQ9VjL5-cJiqiS0ljE1~jzcU5*1 0L1k0=1(i_bwcijO4UbI93gX4!bc0Rb/36cy5g1 2WhYikh#12jZh*hkj%j)bo1wj,aJiu4!gUc$cZjo9!g%c9aKh1bEa8i2h*jB0~ciclj)jGibkzadcShGhfc 2X9(1s12bmj40|i+0$cyhXb{j_gF9a9-5e0dkb0l760l0fcM3;jK8X5-cs1wjQezc%9 hPhR1ba|j.0Ab}i}aWjC0$jtiL0%9;9MaabV366z1lhBi,151bcy129}jIcoh@2%bc0#h.93bmkM7g17b}2Ulyi/hwi@hUaaaPax0Li(0t2B5y1 6-jpc.3/c:261^2E79c_2L2Nc}kLiJ2Qd40vd665d83`da4EdcfXdeg3dhd?dldn4|dq1?dsg8fSfKe1fMj75gewgbeA8sfMjQgp75ed560,e(827Ef5fReQ8Ned6k8-f^gM5Zf.msd(lpmlf+5;e_gQf6eUf`5~ml7263df8dewd{f/4q6k6mm70ogc8@d/fng4f36GmIe2mOmw5ue:6Qf=8Ff2m5fQmJ6,gcfk6Jefggf4md76edfciw9=iym0mngB8=gLd(bnm;e2gkm3fuiOe+m=exmd7Wmp8+7#957sfX7+j|gzmom98=7t7^lNnb8g1endmm8ImygomY8lnm1eno3G06f*mWmvgRfukbm-e`nTdy7Cnadf74hNn47B8za(frm87$7%geegnY81nVnJgqmYmqewn6n7mA6@gNgGmY9ef%ntn/mam_o2f!o4gT9hml1giz4!gZ4H4R9E0k0pl8ag2Al6a@c8he9-9/g,at9@9_kAb09}jaiI9{aa0Halj(h%huksicdAh*2!lnh?mkipb0lEa6c9b.l20Qhgl*2!h4d02H0La@kXb20v2%0(1.280c0S0b0`0`0(0.0:0Y0L0@1ceN0L0$0:3;0/0`p3p50`9g0L0roH0$5 fG1 aIcjaaiWhsoOi+0dav2mh(pl0gez0$04kpoh0|0~ct04.