Huile noire

Après les évènements de la base aérienne de Fort Wiekamp, en 1997, Mulder est parvenu à isoler un échantillon d'Huile Noire, cette entité extra-terrestre qui s'apparente à un virus. Il a fallu d'infinies précautions pour obtenir ce résultat. Mulder souhaite que Scully étudie le fonctionnement de ce liquide car, même si les Russes semblent posséder un vaccin, il pense que les États-Unis devraient développer leur propre antidote indépendamment.

Les recherches de Scully montrent que l'huile est composée de cellules primitives de deux types seulement qu'elle a appelés blanche et noire du fait de leur apparence au microscope. Chaque cellule se développe en suivant des règles très simples en fonction du type des cellules adjacentes. Dana développe son fonctionnement en considérant une suite de cellules en une seule dimension (que l'on va appeler dans la suite «échantillon»), qui est régi par les règles suivantes :

Ces règles indiquent, pour chaque triplet de cellules, comment évolue la cellule du milieu.

Supposons que l'état de l'échantillon est :

Pour les cellules extrêmes, on considère que la séquence se referme : la voisine de gauche de la cellule à l'extrémité gauche est la cellule située à l'extrémité droite et inversement.

En appliquant les règles qu'a déterminées Scully à l'échantillon, on obtiendra à la génération suivante :

Vous êtes chargés d'aider à comprendre son fonctionnement par des travaux de simulation de l'évolution de certains échantillons. Pour simplifier les travaux, plutôt que de manipuler des couleurs pour les types de cellule de l'échantillon, on peut associer un nombre. Pour cela, on considère qu'une cellule «noire» vaut 1 et une cellule «blanche» vaut 0. Il ne reste plus qu'à lire le nombre en binaire. Dans l'exemple qui précède, donne l'écriture binaire 0110100 et donc la valeur 52 (c'est la valeur de l'état de l'échantillon).

La description de l'échantillon est donnée en entrée du problème. Trois valeurs sont indiquées :

• depart : valeur de l'état de l'échantillon à l'instant initial
• taille : nombre de cellules dont est composé l'échantillon
• etapes : nombre d'étapes de simulation à réaliser

La réponse à fournir est la valeur numérique qui correspond à l'état de l'échantillon après avoir réalisé le nombre d'étapes indiquées.

Par exemple, si depart vaut 93 et taille vaut 8, l'échantillon a pour état : □■□■■■□■. Si etape vaut 6, il suffit de réaliser 6 transformations. Après une étape, l'état de l'échantillon sera (étape 1) : ■■■■□■■■. Encore une étape, et on obtient (étape 2) : □□□■■■□□. Après 6 étapes, l'état de l'échantillon sera : ■■□□■■□■. Cet état correspond au nombre 205. Pour les entrées depart : 93, taille : 8 et etapes: 6, on validerait donc le défi avec la valeur 205.