Hercule 3 : La biche de Cyrénée

Histoire

Pour son 3e travail, Eurysthée demanda à Hercule de capturer la biche aux pieds d'airain qui s'était enfuie de l'attelage d'Artémis.

La biche appartenant à Artémis, Hercule ne pouvait pas lui faire de mal sous peine de devoir essuyer la colère de la déesse. Il décida donc de l'épuiser en lui donnant la chasse dans les bois d'Oénoée. Toutefois, il dut veiller à ce qu'elle ne meure pas d'épuisement sans quoi il aurait alors dû affronter Artémis. Hercule estima que, pour avoir les meilleures chances de capturer la biche, il fallait que cette dernière traverse le bois en parcourant un nombre très précis de kilomètres. Ni plus, car elle aurait pu mourir d'épuisement, ni moins, car elle aurait eu encore suffisamment d'énergie pour échapper à Hercule au pied du mont Cyrénée.

Problème

Le bois dans lequel Hercule va s'aventurer est formé d'allées perpendiculaires les unes aux autres. Le bois se traverse en allant de la façade nord vers la façade sud. À chaque embranchement, on peut choisir d'aller à l'est ou à l'ouest. Hercule a relevé les positions des embranchements sous la forme d'une série de nombres. Vous devez indiquer à Hercule la liste des choix de direction qu'il doit réussir à imposer à la biche pour qu'elle ait parcouru, au sortir du bois, exactement le nombre de kilomètres souhaité, sachant de plus qu'elle ne revient jamais sur ses pas.

Exemple

Voyons ce que cela donne avec une petite forêt. Hercule et la biche partent du point A, le point d'entrée unique situé au nord, et ils doivent sortir de la forêt par un des 8 points situés au sud de la forêt.

Pour repérer les positions des chemins, Hercule a procédé ainsi. Le point de départ est situé à l'abcisse 0. Un point qui est situé 1 km à l'est est à l'abscisse 1 et un point situé, par exemple 2 km à l'ouest du point de départ est à l'abscisse -2. Sur la figure suivante, on a relevé les abscisses de chacun des carrefours :

Puis, ces valeurs sont relevées en les lisant ligne par ligne, de haut en bas :
0, -8, 2, -12, -6, -3, 3, -14, -11, -10, -5, -4, 1, 2, 4
Enfin, chaque petit tronçon vertical a une longueur d'1km.

Imaginons qu'Hercule veuille traverser le bois en parcourant précisément 12 km. Il pourrait par exemple emprunter ce chemin :

Dans ce cas, pour aider Hercule, il suffirait de lui dire, pour chaque carrefour, s'il faut prendre à l'est (E) ou à l'ouest (O). Dans notre exemple, les indications à communiquer à Hercule seraient simplement : EOO

Testez votre code

Si Hercule avait fait ce relevé :
0, -4, 9, -5, -1, 3, 12, -6, -4, -2, 0, 2, 9, 11, 13
et si la distance à parcourir avait été 12 km, alors une réponse correcte aurait été : OEO. En effet :

Notez au passage qu'il peut y avoir plusieurs solutions. Dans notre exemple, la réponse OEE aurait aussi été convenable.

Défi

Voici le relevé qu'a fait Hercule :
0,-358,1535,-506,449,1010,1897,-537,-122,238,626,903,1364,1835,2027,-653,-431,
-266,-119,83,306,444,686,824,1057,1194,1424,1600,1837,2016,2230,-671,-594,-501,
-430,-334,-233,-161,-79,35,120,195,318,438,524,627,703,794,899,1015,1086,1187,
1285,1353,1425,1544,1650,1764,1851,1945,2035,2133,2233,-691,-660,-601,-556,-524,
-489,-431,-409,-353,-312,-252,-232,-193,-144,-98,-63,-21,36,91,128,167,239,287,
351,393,457,507,547,596,635,692,712,783,813,871,927,965,1020,1067,1096,1174,
1201,1260,1297,1322,1373,1418,1468,1529,1588,1649,1680,1720,1766,1809,1856,1911,
1961,1998,2049,2126,2161,2212,2251,-706,-689,-664,-640,-623,-598,-575,-552,-536,
-513,-497,-459,-437,-427,-414,-394,-377,-349,-319,-296,-273,-251,-236,-216,-194,
-170,-149,-139,-121,-95,-79,-43,-30,-13,21,40,75,106,117,137,161,200,234,266,
277,315,338,358,369,395,413,458,481,512,533,560,595,611,628,651,677,694,711,737,
763,785,808,830,863,887,919,940,961,978,1010,1040,1062,1073,1092,1104,1136,1184,
1193,1207,1226,1273,1288,1302,1319,1348,1372,1398,1412,1426,1455,1494,1519,1557,
1581,1603,1619,1651,1671,1687,1701,1735,1751,1776,1800,1829,1851,1858,1882,1920,
1944,1970,1996,2016,2040,2076,2096,2130,2153,2190,2210,2228,2250,2269,-718,-705,
-697,-682,-668,-654,-644,-638,-625,-611,-603,-595,-577,-564,-556,-547,-538,-530,
-516,-511,-502,-480,-462,-449,-443,-435,-429,-422,-416,-411,-397,-390,-383,-368,
-355,-347,-335,-310,-301,-285,-280,-270,-258,-248,-240,-235,-222,-213,-205,-192,
-172,-165,-154,-147,-142,-138,-129,-118,-97,-91,-80,-63,-51,-42,-33,-28,-14,1,
17,34,39,46,69,80,89,107,115,128,135,146,160,171,182,203,227,236,259,267,275,
287,300,317,333,344,354,359,367,380,390,401,412,418,442,460,477,486,500,520,530,
541,556,562,588,598,608,618,626,636,649,665,672,682,689,696,701,712,731,742,760,
767,780,791,801,816,826,839,847,867,880,903,917,921,939,944,954,966,975,988,
1008,1012,1033,1049,1056,1065,1070,1076,1087,1096,1103,1112,1134,1148,1178,1185,
1191,1197,1204,1210,1219,1251,1261,1276,1286,1293,1299,1310,1317,1328,1340,1349,
1360,1376,1395,1399,1404,1415,1424,1437,1448,1467,1477,1505,1517,1535,1555,1562,
1575,1583,1588,1607,1617,1627,1641,1655,1665,1676,1683,1688,1698,1702,1729,1739,
1744,1756,1768,1777,1793,1805,1828,1834,1848,1852,1857,1864,1877,1883,1908,1922,
1935,1956,1961,1979,1987,1999,2009,2021,2033,2043,2064,2080,2095,2116,2125,2132,
2139,2165,2184,2192,2205,2220,2225,2231,2244,2254,2262,2270,-719,-717,-714,-702,
-699,-693,-691,-677,-670,-664,-661,-652,-646,-641,-639,-634,-626,-624,-612,-610,
-604,-598,-596,-590,-581,-574,-570,-561,-558,-554,-549,-545,-539,-534,-531,-528,
-525,-514,-512,-509,-505,-500,-498,-467,-463,-458,-456,-448,-444,-442,-438,-433,
-431,-426,-423,-421,-418,-415,-413,-410,-406,-395,-391,-389,-386,-379,-376,-367,
-363,-351,-348,-345,-336,-334,-319,-305,-302,-292,-288,-284,-281,-279,-272,-265,
-261,-252,-249,-247,-242,-239,-236,-229,-226,-220,-214,-212,-209,-204,-201,-182,
-178,-168,-166,-163,-156,-153,-148,-146,-144,-141,-139,-137,-131,-127,-120,-107,
-100,-96,-92,-88,-84,-73,-70,-58,-54,-47,-44,-41,-34,-31,-29,-27,-15,-10,-1,3,
16,20,24,35,37,41,44,51,68,70,79,82,86,91,94,108,113,116,126,129,132,140,145,
149,152,162,170,177,181,186,198,206,224,229,231,240,255,261,264,269,274,279,284,
289,299,309,315,327,330,334,342,345,347,355,357,361,363,372,376,385,387,395,399,
402,411,413,415,421,426,446,453,461,475,478,485,491,498,504,515,523,529,531,535,
547,554,558,561,571,584,589,597,599,606,610,617,619,621,632,635,640,646,660,664,
668,671,673,681,685,687,691,693,698,700,708,711,715,717,732,738,747,759,763,766,
769,779,781,789,792,800,802,815,817,825,828,838,843,846,849,866,868,879,884,900,
904,916,918,920,930,937,940,943,948,953,956,959,970,973,976,986,1005,1007,1009,
1011,1016,1030,1034,1047,1052,1055,1057,1064,1067,1069,1072,1075,1078,1080,1088,
1095,1097,1100,1106,1109,1120,1128,1142,1146,1152,1177,1180,1184,1188,1190,1192,
1194,1199,1201,1205,1209,1211,1214,1223,1249,1253,1260,1263,1273,1281,1283,1288,
1291,1294,1297,1301,1309,1311,1313,1318,1323,1331,1336,1341,1348,1351,1356,1369,
1374,1380,1394,1396,1398,1400,1403,1405,1414,1416,1423,1426,1436,1438,1447,1451,
1464,1470,1475,1485,1504,1506,1515,1523,1531,1542,1552,1558,1560,1565,1573,1576,
1578,1585,1587,1597,1606,1608,1614,1619,1623,1629,1640,1642,1653,1656,1660,1668,
1675,1678,1680,1684,1686,1692,1697,1699,1701,1703,1725,1731,1737,1740,1743,1745,
1755,1757,1766,1774,1776,1782,1791,1797,1803,1806,1825,1829,1832,1836,1847,1849,
1851,1853,1856,1859,1862,1867,1870,1879,1882,1884,1904,1909,1920,1924,1930,1943,
1954,1957,1959,1963,1978,1980,1985,1988,1993,2001,2008,2010,2016,2026,2030,2039,
2042,2044,2061,2065,2079,2081,2087,2102,2113,2120,2124,2126,2131,2133,2136,2152,
2163,2166,2176,2186,2190,2194,2204,2208,2219,2222,2224,2226,2230,2235,2243,2247,
2250,2258,2261,2263,2267,2275

La distance à parcourir vous est donnée en entrée du problème. Aidez Hercule en lui donnant la liste correcte des directions à prendre à chaque carrefour.
Ce problème est tiré de c0d1ng UP 2015

Type de retour

une chaîne de caractères

Entrée du problème

1461

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup15 structure de données combinatoire