Le vaisseau du collectionneur

Des hauts et des bas, mais pas trop...

Le collectionneur fait voler son vaisseau spatial à l'aide de flacons contenant un combustible spécial. Les flacons bleus font monter le vaisseau, et les flacons rouges le font descendre. Plus le flacon est grand, plus le vaisseau monte (ou descend).

Les flacons sont disposés en file sur un rail et à chaque fois que le flacon utilisé est complètement vide, un autre est saisi par une pince mécanique et inséré dans la chambre à combustible. Toutefois, à chaque instant, la pince mécanique ne peut saisir que le flacon le plus à gauche ou le plus à droite (c'est-à-dire un flacon qui est au bout).

La file de flacons est modélisée par une séquence de nombres indiquant la contenance de chaque flacon. Le nombre sera positif pour un flacon bleu et négatif pour un flacon rouge.

Par exemple, la liste de flacons pourrait être :

[1, -6, -2, -1, 4, 4, -3]

Les flacons pourraient être utilisés dans l'ordre : 1, -6, -3, 4, 4, -2, -1. Dans ces conditions, en partant de l'altitude h, le vaisseau du collectionneur passerait successivement par les altitudes : h+1, h-5, h-8, h-4, h, h-2, h-3. Autrement dit, le vaisseau oscillerait entre les altitudes h-8 et h+1, ce qui fait une amplitude de 9.

L'objectif du collectionneur est de programmer son vaisseau de manière à ce que les flacons soient saisis dans un certain ordre, de telle manière que l'amplitude de vol soit minimale. En effet, pour préserver ses collections, il souhaite limiter au maximum les variations d'altitude. Dans le cas où plusieurs possibilités donnent des amplitudes de vol équivalentes, il préférera saisir le flacon le plus à droite (plutôt que celui qui est le plus à gauche).

Pour l'exemple donné plus haut, la solution serait de prendre les flacons dans cet ordre :

[-3, 4, 1, -6, 4, -1, -2]

Ainsi, le vaisseau du collectionneur passerait par les altitudes :

h-3, h+1, h+2, h-4, h, h-1, h-3

L'amplitude vaudrait donc 6.

Pour valider le défi, entrez la séquence de prise des tubes qui satisfait à toutes les conditions. Dans l'exemple où les tubes sont : [1, -6, -2, -1, 4, 4, -3], il faut donc répondre [-3, 4, 1, -6, 4, -1, -2] pour valider le défi.

Ce problème est tiré de c0d1ng UP 2016

Type de retour

une séquence de nombres entiers

Entrée du problème

[8, 30, 12, 27, -41, -46, -40, 0, 12, -17, 12, 1, -45, -32, -50, -36, 8, 8, -35, -7, 41, 41, 34, -15, 7, 48, -19, 13, -41, -42, 35, 19, -27, -22, 40, -6, 23, -4, -15, -8, -37, -12, 26, 3, 35, -10, 31, 5, 13, -17, 21, -40, -22, 30, -29, 29, 13, 23, 17, -4, 34, 24, -8, -25, 33, -43, -36, -33, -48, 7, 11, -12, -9, -47, 35, -25, -4, -48, 23, 43, -31, 46, -49, 33, -50, 48, -4, 0, -28, -12, 38, -1, -50, -39, 3, 45, 7, 50, 34, -28]

Formulaire de réponse

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

Tags : cup16 numérique récursivité combinatoire