Les hybrides II (S01E09)

Mulder et Scully ont été informés de l'existence d'un laboratoire de recherches gouvernemental sur la création d'hybrides par combinaisons de matériels génétiques de différentes provenances (la ou les provenances sont classifiées) afin d'obtenir un nouveau matériel génétique qui possède certaines caractéristiques.

On modélise le problème ainsi :

1. Chaque matériel génétique est décrit par une séquence de 0 et de 1 indiquant si ce matériel génétique possède (1) ou ne possède pas (0) chacune des caractéristiques. Par exemple, si on s'intéresse à 7 caractéristiques, un matériel générique particulier peut être décrit par la série de 7 chiffres 0110100, ce qui indique qu'il possède les propriétés 2, 3 et 5 mais ne possède pas les propriétés 1, 4, 6 et 7. Cette séquence peut aussi être lue comme un nombre entier écrit en binaire et peut donc être résumée par le nombre 52 (car en binaire, il s'écrit 0110100).
2. Dans du matériel génétique de base, chaque caractéristique ne peut apparaître qu'une seule fois (c'est pourquoi le codage avec 0 ou 1 est suffisant).
3. Lorsqu'on combine deux matériels génétiques, les caractéristiques du matériel génétique résultant sont les sommes des caractéristiques des deux matériels combinés. Dans un matériel génétique fabriqué, chaque caractéristique peut donc potentiellement apparaître plusieurs fois. Par exemple, si on combine 0110010 et 0011011, on obtient 0121021.
4. On souhaite fabriquer un matériel génétique qui contient au moins certaines caractéristiques. Par exemple, on pourrait vouloir synthétiser le matériel génétique 0120011. Dès lors qu'on obtient au moins ces caractéristiques le nombre de fois spécifié au minimum, alors, c'est réussi. Par exemple, combiner 0110010 et 0011011 donne 0121021, qui contient au moins 0120011, et la combinaison est donc satisfaisante. Par contre, combiner 0100010 et 1011011 donnerait 1111021, qui n'est pas satisfaisant pour l'objectif 0120011 car la propriété 3 n'apparaît qu'une fois au lieu des deux nécessaires.
5. Le second objectif est de minimiser le nombre de matériels génétiques à combiner pour atteindre le résultat précédent.

En aidant Mulder et Scully à trouver les solutions (il peut y en avoir plusieurs) au problème, ils pourront prévoir quels sont les matériels génétiques à dérober au laboratoire pour l'empêcher d'arriver à ses fins.

Par exemple, si l'entrée décrit les matériels génétiques suivants : 58, 50, 42, 35, 67 et l'objectif 0111021 alors les deux solutions sont de combiner 58 et 35 ou encore 58 et 67. En effet, les matériels génériques sont :

58 : 0111010
50 : 0110010
42 : 0101010
35 : 0100011
67 : 1000011

En combinant 58 et 35, on obtient 0211021 qui satisfait l'objectif. En combinant 58 et 67, on obtient 1111021 qui satisfait aussi l'objectif. Toutes les autres combinaisons qui satisfont l'objectif impliquent strictement plus de 2 matériels génétiques et sont donc moins bonnes.

Le défi sera validé en donnant une des deux solutions 58, 35 ou bien 58, 67.

L'entrée du problème donne la liste des nombres codant les caractéristiques des divers matériels génétiques (mat) , ainsi que l'objectif à atteindre (obj).