Validation de contraintes binaires et de somme

L'objectif consiste à déterminer l'existence de deux entiers x et y satisfaisant simultanément les conditions x + y = s et x & y = a. En exploitant l'identité arithmétique fondamentale x + y = (x ^ y) + 2 * (x & y), on isole directement la composante XOR : x ^ y = s - 2a. Cette décomposition impose deux restrictions strictes pour qu'une configuration soit réalisable :

• La valeur s - 2a doit rester positive ou nulle, un résultat négatif indiquant une impossibilité physique dans le domaine des entiers non signés.
• Les bits activés dans a (intersection) et s - 2a (différence symétrique) doivent être mutuellement exclusifs. Par conséquent, l'expression (s - 2a) & a doit strictement retourner zéro.

Ces vérifications permettent de statuer sur la faisabilité en temps constant, sans itération sur les bits.

#include <iostream>

void evaluate_bitwise_constraints() {
    long long intersection, total_sum;
    std::cin >> intersection >> total_sum;

    // Extraction de la composante XOR via l'identité arithmétique
    long long xor_component = total_sum - (intersection << 1);

    // Validation : pas de sous-écoulement et absence de conflits de bits
    if (xor_component < 0 || (xor_component & intersection) != 0) {
        std::cout << "No" << '\n';
    } else {
        std::cout << "Yes" << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int cases;
    if (std::cin >> cases) {
        while (cases--) {
            evaluate_bitwise_constraints();
        }
    }
    return 0;
}

Maximisation séquentielle par critère d'échange et DP

Pour une séquence d'évaluations récursives de la forme res = res * a_i + b_i, l'ordre d'application des paires (a_i, b_i) détermine la valeur finale. L'analyse comparative de deux éléments adjacents i et j révèle que l'inversion de leur ordre améliore le résultat si (a_i - 1) * b_j > (a_j - 1) * b_i. Ce principe de tri greedy élimine la nécessité d'exploration stochastique.

Une fois la collection ordonnée selon cette propriété, une programmation dynamique de type sac à dos optimisé calcule la valeur maximale. Le tableau dp[j] mémorise le meilleur score atteignable avec exactement j opérations. Le parcours en ordre décroissant de j garantit que chaque élément n'est utilisé qu'une fois par état.

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

struct Operation {
    long long multiplier;
    long long additive;
};

// Comparateur fondé sur la propriété d'échange optimale
bool compare_operations(const Operation& lhs, const Operation& rhs) {
    return (lhs.multiplier - 1) * rhs.additive > (rhs.multiplier - 1) * lhs.additive;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    if (!(std::cin >> n >> k)) return 0;

    std::vector<Operation> items(n);
    for (auto& item : items) {
        std::cin >> item.multiplier >> item.additive;
    }

    // Tri préalable selon la condition mathématique dérivée
    std::sort(items.begin(), items.end(), compare_operations);

    // dp[j] stocke le résultat maximal après j opérations sélectionnées
    std::vector<long long> dp(k + 1, 0);
    dp[0] = 1; // Valeur identité initiale avant toute transformation

    for (const auto& op : items) {
        for (int j = k; j >= 1; --j) {
            long long candidate = dp[j - 1] * op.multiplier + op.additive;
            if (candidate > dp[j]) {
                dp[j] = candidate;
            }
        }
    }

    std::cout << dp[k] << '\n';
    return 0;
}