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

.128013s3_8èufv»Iy 7naêSû1me(P4C2:tw«i]D[hE)6Oo;bcdUg/T0làqp!.rF-,À}=+Nk{95Rxé050S0v0C0p0F0Y0b0m0R0Y0p0b0b0.010C0F0#010406050b0g0u0u0p0(0l040r0O0Y0g1b0O0o0m020p0u0#0P0m0^0v1l0(0!0g0v0b050V1i1k1m1o1g0#041M1T051W0V1W1Y1T1g0S0F0i131517190J0F0U0J0Y1:0J0C1e050~0Q0Y0v1+1618011/1;1?1;0C1|1~1`0C0Q0O0S1o1{0(1U0C0J131r0b0#0p0o190A01201-010h100v0o1z0v1`2o2q2v222y1~2B0u2D040a0m0x0(0O0#0O0b0F1u1w0|2m0(0(0v0R2Y1M2F0o1U0V2k2.0C2i2h2j0S2H191?0o2A2V1`1(1*14212{0F2}0o2e1)1`0#2%1U2,2.3f1h2p1w332w380(1l0Y1e0m0t2+3j1f3i2G3l223n3p3r0A3u2q3w2,2`013B0p3q040m0c3F2-1g3I3z193L3N0m0y3R3H3j3J3X3r0@3#3T3%3V3K0O3o3M3r0M3,3x3k1,3A3;3C3O0n3_3U3|3W3~3?3O0e423.443:3=3Y0?4a3y4c3)040t0X4h3{344d3 0t3t1N3v3-4i4q4k0t3E4v3G1V3d1M312;0S2^3J0R2e2N0{1)1U3c0v3e3v3#054N0|4V4y2w0;1e0|0h4X434q0D3r4,4b4z0h1e1K0C0d0~0b0d0i3M0F0|4;4$221d040w534p3m1e2S0Y1~0(1L4D2-3`3J560L0B3,0m5q0m5k3/0o1e2p0F2%5h3f5s4-2w0O1e0.3#5C4=2w560I593J0u0F1e4n5i3O5t4c4(040h3;5I5W4z5w0O360C0g2%5$5D220O4/04365/5K3A0Q5c2q0U0v5O3/56585U5%2w5Q1e0c3^655:19560+5_541968040y416c5`6e1e0L0G5p5r66225Y5!0(6h5a3A1e5 0o5.6o6i016f6B3(5)5+5-605U5J6J5=1e5^6S6w3W5c1r5f5A4W6d6K1e5o5U065r6:6T6C195Y0F4+6Y6*5v046F6H5B6Z015F040.5H6{6p010b2t04010U0p0g0R0J2D614c566-3f6/6;7r726}5x5z7l4q5M7x5b042U6P703v6=3J740*6M3/6k6a7A551e6t786U1e0/77716*6k4u7p7r5q725Y0v116R3h6*7n6u7%6v6|5w0 7w6I6?6+045N7{6N7C5*0o5,7F3G7H3/7J7L4c7N6b7.79567S7Y797J7X7G727!3,7q7(6*6y5#7T7|6}4 1~5-8b4q6V5@0o8C7B7v1K7P6q047o4w7=7)6W6`8j6J8y3M0v8B8w7I1e0$8m878o5R045T8f6J7:6.7=6:8R042%858G8!3/0;0R1e0)3M0b7-8P7?795Y8_5-8{8U7|8~1e0W0(1J3_0V4Z4U4F9m0V4I1M0C4K9r2?2/2d2f2;0p1}9o4I1S4#7|2%0u0d0h0p0;0v0d0J0c1e1E1G1I1K0m8O4E1Z3w1T0T2}0m4T5Q0f2%0m0p0#3c0O7i1 4N0o2W0b0C1 0Z9W1V3w0g0Y3w1?040b0`2p2%0(0m1~122p1b9^0m930Y1vab8Yaa6 1 0w7f7h7j0m0O0g0m0S2S2X0L0m0P1Ma41ga42=0F0vaa7i0p0R0g9%0|120|0g0_ab0F9`9V0O0Q9{0o1J12aD0VaF05a40b00216Qaa9UalaS8YaV1?aY121v0Cab0p0m0u0q2Mab1v0U1J5-0%0m0H2q121~13162m840(7_1 ak0#8Yb01(2%2)1F2Ab02%0o0i0O0laK5s9l04917,1MbGaCaE0Fa3bO4N1A1mbEac0m0`0Y0`2M84a_130J0pa@a|9{axbfab003;ay9?az172qb00Bah0Fa^bWbYb!0Cb$b4b6361(0R1 0Sb.aMb*aXb,0ob:849(bj15b3b51 7D846Q0m10129%bq0g0ibxcj120q2=1 9.a80F0`120}b10m5!0o2)0Fbpbr0mbzbBbDaa4Y4ObH926RbG0%bN3w0Va13w313J241=1@1_9F3J2J2A2C1e2P0r0R0(1cb00x0l2k1v4X4T9F3g4WbG8@4*8L015?5s805u4@044_4{164~5052dj7m1e648.8x6#5eaK6(4E7/6r9X3S8?7@6~7g9=dC2-884c748(dO7t5|a53;9{0Sdf637 dx81cp85948)8t1e6z8H7Q57df6}aod!1e6g8|4j6Ocq865jdE040Ld:198E6X9c815d6%e5016^8T8ndJd^d|8D5GdS5V6*7b1e7edL7j01d_040Ge48;968V4)azc2eddRed0odV0bdX0vdZdt7ydvd$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{8VdVbm0o5 frd?fp2Af~fI3K6Eetfxd%e-e35n7;6;8@6_f2ardMeweSfLfu0FfheGfDf2fOeFg37zg36}gngu7RfUf*fWflfY8`f#90c#fjeB9d5cfZ0(f@d,97f$9g9i6.bKcZ9n2.9D1X040z0}b,cF2S9=9(0(cIbx1 0o0`2q0u83bg00369@0i0`0oaJci2!aIbU9VaTa{ce1Kbcg(281 0`0~bq0m4_2m0s9{0g93hj1w380u0Q9,0Sb:0#0`bm2YcJb0cwb0cC9,0`0i2X0`0vc(9Z9E0N1w1t10aXc91v0R9-1tb_ax9?0O1Ahn5g0m1Ig|0Y0m0l9-h#9(eW6QaS6_0hhzg;hCb/bp1m4N5-b00Y002A93htbhaRcT6$dBbc0xavaLb(aO0o0+ahh-hj9`axawaobFcZesfwev9kcZimakg}g/c11 bhbR0#h)h=0bb2d)6Qim2W381wakcl0S0`c bZg;hc1 cNcP1v2}c1cT1Ki89B0m069}i5hSa|0p2Yax00aPco2z9Wau1w1F0#i bVebdB0m0E0mghat0jiB2Za7j59Vjags0m0jhN1$g$0K1w2y2Zcoi1ih0bjf0m9{aYcLa%5ehKh=cc1J0m8zamh=cY4!8J5hc%0m0rb}i?aQ9VjL5-cJiqiS0mjE1~jzcU5*1 0F1k0`1(i_bwcijO4UbI93gX4!bc0,b/36cy5g1 2WhYikh#12jZh*hkj%j)bo1wj,aJiu4!gUc$cZjo9!g%c9aKh1bEa8i2h*jB0~ciclj)jGibkzadcShGhfc 2X9(1s12bmj40|i+0pcyhXb{j_gF9a9-5e0wkb0m760m0XcM3;jK8X5-cs1wjQezc%9 hPhR1ba|j.0Rb}i}aWjC0pjtiL0C9;9MaabV366z1lhBi,151bcy129}jIcoh@2%bc0kh.93bmkM7g17b}2Ulyi/hwi@hUaaaPax0Fi(0o2B5y1 6-jpc.3/c:261^2E79c_2L2Nc}kLiJ2Qd40Jd665d83`da4EdcfXdeg3dhd?dldn4|dq1?dsg8fSfKe1fMj75gewgbeA8sfMjQgp75ed560=e(827Ef5fReQ8Ned6k8-f^gM5Zf.msd(lpmlf+5;e_gQf6eUf`5~ml7263df8dewd{f/4q6k6mm70-gc8@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!gZ4H4R9E0:0Ol8ag2Al6a@c8he9-9/g,at9@9_kAb09}jaiI9{aa0jalj(h%huksicdAh*2!lnh?mkipb0lEa6c9b.l20uhgl*2!h4d02H0Fa@kXb20J2%0h1.280#0b0B0V0V0h0(0%0D0F0;1ceN0F0p0%3;0U0Vp3p50V9g0F0doH0p5 fG1 aIcjaaiWhsoOi+0wav2mh(pl0vez0p04kpoh0|0~ct04.