Présentation du Problème

Nous sommes confrontés à un ensemble de $N$ lampes, initialement toutes allumées. Nous disposons de quatre boutons distincts qui modifient l'état de ces lampes. Chaque appui sur un bouton inverse l'état (allumée devient éteinte, et vice-versa) des lampes affectées. Les actions des boutons sont les suivantes :

• Bouton 1 : Inverse l'état de toutes les lampes.
• Bouton 2 : Inverse l'état des lampes dont le numéro est impair (1, 3, 5, ...).
• Bouton 3 : Inverse l'état des lampes dont le numéro est pair (2, 4, 6, ...).
• Bouton 4 : Inverse l'état des lampes dont le numéro est de la forme $3k+1$ pour $k \ge 0$ (par exemple : 1, 4, 7, 10, ...).

Étant donné le nombre total de lampes $N$, le nombre maximal d'appuis sur les boutons $C$, et l'état final requis pour certaines lampes (certaines doivent être allumées, d'autres éteintes, et d'autres encore n'ont pas d'exigence spécifique), l'objectif est de trouver toutes les configurations finales possibles des lampes qui satisfont ces conditions, et de les afficher par ordre lexicographique.

L'outil Bitset

Pour gérer les états des lampes (chaque lampe peut être soit allumée, soit éteinte, soit 1 ou 0), l'utilisation d'un std::bitset en C++ est particulièrement adaptée. Un bitset est une structure de données qui représente une séquence de bits. Chaque bit occupe un espace minimal (1 bit), ce qui le rend très efficace en mémoire par rapport à d'autres conteneurs.

Opérations Essentielles de std::bitset :

• mon_bitset.reset() : Met tous les bits à 0 (éteint toutes les lampes).
• mon_bitset.set() : Met tous les bits à 1 (allume toutes les lampes).
• mon_bitset.test(i) ou mon_bitset[i] : Retourne la valeur du bit à l'indice i (0-indexé).
• mon_bitset.any() : Retourne true si au moins un bit est à 1.
• mon_bitset.none() : Retourne true si tous les bits sont à 0.
• mon_bitset.count() : Retourne le nombre de bits à 1.
• mon_bitset.flip() : Inverse tous les bits (chaque 0 devient 1, chaque 1 devient 0).
• mon_bitset.flip(i) : Inverse l'état du bit à l'indice i.

Modélisation des Opérations des Boutons

Nous pouvons implémanter les actions de chaque bouton comme des fonctions prenant un std::bitset représentant l'état actuel des lampes et retournant le nouvel état après l'activation du bouton. Supposons une taille maximale de 100 lampes pour notre bitset, représentée par la constante MAX_LAMPES.

#include <bitset>
#include <vector>
#include <algorithm>
#include <iostream>

const int MAX_LAMPES = 100; // Taille maximale du bitset

// Inverse l'état de toutes les lampes
std::bitset<MAX_LAMPES> op_toutes_lampes(std::bitset<MAX_LAMPES> etat_actuel, int N) {
    return etat_actuel.flip(); // `flip()` sans argument inverse tous les bits
}

// Inverse l'état des lampes impaires (1-indexées)
std::bitset<MAX_LAMPES> op_lampes_impaires(std::bitset<MAX_LAMPES> etat_actuel, int N) {
    for (int i = 0; i < N; ++i) { // i est 0-indexé
        if ((i + 1) % 2 != 0) { // Si la lampe est impaire (1-indexée)
            etat_actuel.flip(i);
        }
    }
    return etat_actuel;
}

// Inverse l'état des lampes paires (1-indexées)
std::bitset<MAX_LAMPES> op_lampes_paires(std::bitset<MAX_LAMPES> etat_actuel, int N) {
    for (int i = 0; i < N; ++i) { // i est 0-indexé
        if ((i + 1) % 2 == 0) { // Si la lampe est paire (1-indexée)
            etat_actuel.flip(i);
        }
    }
    return etat_actuel;
}

// Inverse l'état des lampes de forme 3k+1 (1-indexées)
std::bitset<MAX_LAMPES> op_lampes_3k_plus_1(std::bitset<MAX_LAMPES> etat_actuel, int N) {
    for (int i = 0; i < N; ++i) { // i est 0-indexé
        if ((i + 1) % 3 == 1) { // Si la lampe est de la forme 3k+1 (1-indexée)
            etat_actuel.flip(i);
        }
    }
    return etat_actuel;
}

Propriétés des Boutons

Une observation cruciale simplifie grandement la résolution : appuyer deux fois de suite sur n'importe quel bouton ramène le système à son état initial, annulant ainsi l'effet de ces deux pressions. Cela signifie que chaque bouton n'a réellement que deux états pertinents : soit il n'a jamais été appuyé (ou un nombre pair de fois), soit il a été apuyé une fois (ou un nombre impair de fois). En conséquence, pour trouver toutes les configurations uniques, il suffit de considérer chaque bouton comme ayant été appuyé au maximum une fois. Il y a donc $2^4 = 16$ combinaisons uniques d'appuis sur les boutons (chaque bouton est soit "utilisé", soit "non utilisé").

De plus, si une configuration peut être atteinte en appuyant sur $K$ boutons (chacun au maximum une fois), et que le nombre total d'appuis autorisés est $C$, alors $C - K$ doit être un nombre pair non négatif. C'est parce que toute pression supplémentaire au-delà de ces $K$ appuis minimaux doit venir par paires (appuyer puis ré-appuyer le même bouton) pour ne pas altérer la configuration finale.

Algorithme de Résolution

L'approche consiste à générer toutes les 16 configurations uniques possibles en activant un sous-ensemble des quatre boutons. Pour chaque configuration générée, nous vérifions deux conditions :

1. Le nombre d'appuis sur les boutons $K$ nécessaire pour atteindre cette configuration satisfait la condition de parité avec $C$ (c'est-à-dire, $(C - K) \pmod 2 == 0$ et $C \ge K$).
2. La configuration respecte toutes les exigences d'état final spécifiées pour certaines lampes.

Pour la vérification des exigences, nous avons besoin d'une fonction :

// Vérifie si une configuration respecte les contraintes données
// 'lampes_fixees_on' : liste d'indices de lampes qui doivent être ON
// 'lampes_fixees_off' : liste d'indices de lampes qui doivent être OFF
bool est_configuration_valide(const std::bitset<MAX_LAMPES>& config, int N,
                              const std::vector<int>& lampes_fixees_on,
                              const std::vector<int>& lampes_fixees_off) {
    for (int idx_on : lampes_fixees_on) {
        if (!config[idx_on - 1]) return false; // La lampe (1-indexée) doit être ON
    }
    for (int idx_off : lampes_fixees_off) {
        if (config[idx_off - 1]) return false; // La lampe (1-indexée) doit être OFF
    }
    return true;
}

// Comparateur pour trier les bitsets lexicographiquement
bool comparer_bitsets(const std::bitset<MAX_LAMPES>& bs1, const std::bitset<MAX_LAMPES>& bs2, int N) {
    for (int i = 0; i < N; ++i) { // Comparaison du bit le plus significatif au moins significatif
        if (bs1[i] < bs2[i]) return true;
        if (bs1[i] > bs2[i]) return false;
    }
    return false; // Sont identiques
}

Le corps principal du programme appliquera ces fonctions :

// Hypothèse : N, C, lampes_fixees_on, lampes_fixees_off sont déjà initialisés
// N: nombre de lampes, C: nombre total d'appuis

int N_lamps; // Nombre de lampes
int C_presses; // Nombre total d'appuis

std::vector<int> lamps_on_required; // Indices 1-based des lampes qui doivent être ON
std::vector<int> lamps_off_required; // Indices 1-based des lampes qui doivent être OFF

// Lecture des entrées N, C, puis les lampes_on_required et lamps_off_required

std::vector<std::bitset<MAX_LAMPES>> solutions_possibles;

// L'état initial est toutes les lampes allumées
std::bitset<MAX_LAMPES> etat_initial_lampes;
etat_initial_lampes.set(); // Toutes à 1

// Itérer sur les 16 combinaisons possibles d'appuis de boutons
// Un masque binaire de 4 bits représente quels boutons sont "activés"
// 0000 -> aucun bouton activé
// 0001 -> bouton 1 activé
// ...
// 1111 -> tous les boutons activés
for (int i = 0; i < (1 << 4); ++i) {
    std::bitset<MAX_LAMPES> config_actuelle = etat_initial_lampes;
    int boutons_appuyes_uniques = 0;

    // Appliquer les boutons selon le masque binaire 'i'
    if ((i >> 0) & 1) { // Si le bit 0 est à 1, appliquer le bouton 1
        config_actuelle = op_toutes_lampes(config_actuelle, N_lamps);
        boutons_appuyes_uniques++;
    }
    if ((i >> 1) & 1) { // Si le bit 1 est à 1, appliquer le bouton 2
        config_actuelle = op_lampes_impaires(config_actuelle, N_lamps);
        boutons_appuyes_uniques++;
    }
    if ((i >> 2) & 1) { // Si le bit 2 est à 1, appliquer le bouton 3
        config_actuelle = op_lampes_paires(config_actuelle, N_lamps);
        boutons_appuyes_uniques++;
    }
    if ((i >> 3) & 1) { // Si le bit 3 est à 1, appliquer le bouton 4
        config_actuelle = op_lampes_3k_plus_1(config_actuelle, N_lamps);
        boutons_appuyes_uniques++;
    }

    // Vérifier la parité du nombre de pressions
    if (C_presses >= boutons_appuyes_uniques &&
        (C_presses - boutons_appuyes_uniques) % 2 == 0) {
        
        // Vérifier si la configuration est valide selon les contraintes
        if (est_configuration_valide(config_actuelle, N_lamps, lamps_on_required, lamps_off_required)) {
            solutions_possibles.push_back(config_actuelle);
        }
    }
}

// Trier les solutions uniques et les afficher
std::sort(solutions_possibles.begin(), solutions_possibles.end(),
          [&](const std::bitset<MAX_LAMPES>& a, const std::bitset<MAX_LAMPES>& b) {
              return comparer_bitsets(a, b, N_lamps);
          });

// Supprimer les doublons après le tri
solutions_possibles.erase(std::unique(solutions_possibles.begin(), solutions_possibles.end()), solutions_possibles.end());

if (solutions_possibles.empty()) {
    std::cout << "IMPOSSIBLE\n";
} else {
    for (const auto& solution : solutions_possibles) {
        for (int i = 0; i < N_lamps; ++i) {
            std::cout << solution[i];
        }
        std::cout << "\n";
    }
}