Digicode – Épreuve régionale 2014

Énoncé¶

Joseph Marchand est encore bloqué devant la porte d'entrée de son immeuble...

Figurez-vous qu'il a encore oublié le code de son digicode. Il a beau se farfouiller dans les recoins de sa mémoire (limitée il faut dire), impossible de s'en souvenir. C'était peut-être « 8 9 11 9 », sinon « 0 4 2 0 », ou encore « 0 0 0 7 », ou alors essayons « 10 3 8 0 »...

Essayant à plusieurs reprises sans succès, il décide donc de rentrer successivement tout les codes possibles sur l'appareil.

Trouvant la tâche longue, il s'aperçoit soudain que le digicode ne possède pas de bouton "annuler", et comprend alors que celui-ci ne prend en compte que les derniers symboles tapés. Cela signifie pour un code à 4 chiffres, lorsqu'il tape « 1 2 3 4 5 6 », les codes « 1 2 3 4 », « 2 3 4 5 » et « 3 4 5 6 » sont vérifiés par le digicode, et qu'ainsi à chaque nouveau symbole tapé un code supplémentaire est vérifié.

Cela pourrait lui faire gagner beaucoup de temps, surtout qu'il doit bien exister un algorithme pour ça ! Et c'est là que vous intervenez :

Soit un digicode composé d'un clavier de N symboles (les nombres de 0 à N-1). Connaissant la longueur du code, L, vous devez renvoyer une plus courte séquence contenant l'ensemble des combinaisons de symboles de taille L.

Entrée¶

• Sur la première ligne, un entier N, le nombre de symboles
• Sur la seconde ligne, un entier L, la longueur du code

Sortie¶

• Sur la première ligne, T, la longueur minimum d'une chaîne contenant tous les codes
• Sur la seconde ligne, T nombres séparés par des espaces représentant la chaîne à taper