Propriétés fondamentales de l'opérateur XOR

L'opérateur XOR (noté ⊕) et l'addition partagent des propriétés liées à la parité des nombres. Pour deux entiers a et b, on a la relation :

a + b = (a ⊕ b) + 2(a ∧ b), où ∧ désigne l'opérateur AND bit à bit. Ainsi, la différence entre la somme numérique et la somme XOR est toujousr un multiple de 2, impliquant une parité identique.

Cela entraîne que pour tout problème où l'on cherche une séquence avec une somme numérique n et une somme XOR m, il est nécessaire que n ≥ m et que n et m aient la même parité. Sinon, aucune solution n'est possible.

Voici une implémentation en C++ pour déterminer une telle séquence. Le code a été restructuré avec des noms de variables modifiés pour améliorer la lisibilité.

#include <iostream>
#include <vector>
using namespace std;

void resoudreProbleme() {
    long long xorCible, sommeCible;
    cin >> xorCible >> sommeCible;
    
    long long difference = sommeCible - xorCible;
    if (difference < 0 || (sommeCible % 2) != (xorCible % 2)) {
        cout << -1 << endl;
        return;
    }
    
    if (xorCible == 0) {
        cout << 0 << endl;
        return;
    }
    
    if (xorCible == sommeCible) {
        cout << 1 << endl << xorCible << endl;
        return;
    }
    
    long long moitieDiff = difference / 2;
    
    if (((moitieDiff + xorCible) ^ moitieDiff) == xorCible) {
        cout << 2 << endl << moitieDiff << " " << moitieDiff + xorCible << endl;
    } else if (((moitieDiff * 2) ^ xorCible) == xorCible) {
        cout << 2 << endl << moitieDiff * 2 << " " << xorCible << endl;
    } else {
        cout << 3 << endl << moitieDiff << " " << moitieDiff << " " << xorCible << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int casTests;
    cin >> casTests;
    while (casTests--) {
        resoudreProbleme();
    }
    return 0;
}

Stratégie dans les jeux de piles de pierres

Dans un jeu où deux joueurs alternent pour prendre des pierres de piles, la condition de victoire dépend des relations entre les piles. Si une pile contient plus de pierres que la somme des autres, le premier joueur peut garantir une victoire en se concentrant dessus.

Dans le cas contraire, le jeu se réduit à analyser la parité de la différence entre la plus grande pile et le reste. Lorsque cette différence est impaire, le premier joueur a un avantage.

L'algorithme suivant détermine le gagnant pour un ensemble donné de piles. Le code a été adapté avec des expressions logiques alternatives et des noms de varibales différents.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void determinerGagnant() {
    int nombrePiles;
    cin >> nombrePiles;
    
    vector<int> piles(nombrePiles);
    long long totalPierres = 0;
    int pileMax = 0;
    
    for (int i = 0; i < nombrePiles; ++i) {
        cin >> piles[i];
        totalPierres += piles[i];
        pileMax = max(pileMax, piles[i]);
    }
    
    for (int i = 0; i < nombrePiles; ++i) {
        if (piles[i] > totalPierres - piles[i]) {
            cout << "w" << endl;
            return;
        }
    }
    
    if ((totalPierres - 2 * pileMax) % 2 != 0) {
        cout << "w" << endl;
    } else {
        cout << "m" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int casTests;
    cin >> casTests;
    while (casTests--) {
        determinerGagnant();
    }
    return 0;
}