Problème A

Énoncé : On vous donne deux entiers \(n\) et \(k\). En une opération, vous pouvez soustraire n'importe quelle puissance de \(k\) (c'est-à-dire \(k^x\) pour \(x \ge 0\)) de \(n\). Trouvez le nombre minimum d'opérations pour réduire \(n\) à \(0\).

Analyse : La solution optimale consiste à représenter \(n\) en base \(k\). Le nombre minimum d'opérations correspond simplement à la somme des chiffres de \(n\) dans cette base. Si \(k = 1\), la seule puissance disponible est \(1^0 = 1\), donc la réponse est directement \(n\).

#include <iostream>

using namespace std;

void solve() {
    long long n, k;
    cin >> n >> k;
    
    if (k == 1) {
        cout << n << "\n";
        return;
    }
    
    long long operations = 0;
    while (n > 0) {
        operations += n % k;
        n /= k;
    }
    cout << operations << "\n";
}

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

Problème B

Énoncé : Il y a \(n\) ampoules numérotées de \(1\) à \(n\), toutes initialement allumées. Pour chaque \(i\) de \(1\) à \(n\), on inverse l'état de toutes les ampoules dont le numéro est un multiple de \(i\). Trouvez la valeur minimale de \(n\) telle qu'exactement \(k\) ampoules restent allumées à la fin.

Analyse : L'ampoule \(i\) est inversée un nombre de fois égal à son nombre de diviseurs. Elle restera allumée si et seulement si ce nombre est pair, ce qui est le cas pour tous les entiers sauf les carrés parfaits. Ainsi, le nombre d'ampoules allumées pour un \(n\) donné est \(n - \lfloor\sqrt{n}\rflooor\). Cette fonction étant strictement croissante, nous pouvons utiliser la recherche dichotomique pour trouver le \(n\) minimal.

#include <iostream>
#include <cmath>

using namespace std;

void solve() {
    long long k;
    cin >> k;
    
    long long left = 1, right = 2e18;
    long long result = right;
    
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        long long lit_bulbs = mid - (long long)sqrtl(mid);
        
        if (lit_bulbs >= k) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << result << "\n";
}

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

Problème C

Énoncé : Étant donné trois entiers \(b\), \(c\) et \(d\), trouvez un entier \(a \in [0, 2^{61}]\) tel que \((a | b) - (a \& c) = d\). Les opérateurs \(|\) et \(\&\) désignent le OU bit à bit et le ET bit à bit.

Analyse : Nous pouvons déterminer les bits de \(a\) indépendamment en examinant chaque position de bit. Pour le \(i\)-ème bit, nous testons si \(a_i = 0\) ou \(a_i = 1\) satisfait l'équation locale. Si aucune valeur ne fonctionne pour un bit donné, il n'y a pas de solution globale.

#include <iostream>

using namespace std;

void solve() {
    long long b, c, d;
    cin >> b >> c >> d;
    
    long long a = 0;
    bool possible = true;
    
    for (int i = 0; i < 62; ++i) {
        int bit_b = (b >> i) & 1;
        int bit_c = (c >> i) & 1;
        int bit_d = (d >> i) & 1;
        
        int bit_a = -1;
        for (int val = 0; val <= 1; ++val) {
            int res = (val | bit_b) - (val & bit_c);
            if (res == bit_d) {
                bit_a = val;
                break;
            }
        }
        
        if (bit_a == -1) {
            possible = false;
            break;
        }
        a |= ((long long)bit_a << i);
    }
    
    if (possible) {
        cout << a << "\n";
    } else {
        cout << -1 << "\n";
    }
}

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

Problème D

Énoncé : Sur une ligne, \(n\) points sont marqués de \(1\) à \(n\). Initialement, il n'y a pas d'arcs. \(m\) opérations sont effectuées, chacune définie par \(a_i, d_i, k_i\), connectant les points \(a_i, a_i+d_i, \dots, a_i+k_i \cdot d_i\) séquentiellement. Trouvez le nombre de composantes connexes finales. On garanitt que \(d_i \le 10\).

Analyse : Puisque le pas \(d\) est très petit, un point \(x\) ne peut être connecté qu'à des points dans un voisinage restreint. Nous utilisons une structure Union-Find. Pour chaque point et chaque pas \(d\), nous maintenons la longueur maximale de la chaîne de connexions vers la droite, ce qui permet de fusionner les ensembles efficacement sans reparcourir toute la séquence.

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

using namespace std;

struct DSU {
    vector<int> parent;
    int components;

    DSU(int n) {
        parent.resize(n + 1);
        components = n;
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }

    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            components--;
        }
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    
    DSU dsu(n);
    vector<vector<int>> max_reach(n + 1, vector<int>(11, 0));
    
    for (int i = 0; i < m; ++i) {
        int a, d, k;
        cin >> a >> d >> k;
        max_reach[a][d] = max(max_reach[a][d], k);
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int d = 1; d <= 10; ++d) {
            if (max_reach[i][d] > 0) {
                int next_node = i + d;
                if (next_node <= n) {
                    dsu.unite(i, next_node);
                    max_reach[next_node][d] = max(max_reach[next_node][d], max_reach[i][d] - 1);
                }
            }
        }
    }
    
    cout << dsu.components << "\n";
}

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

Problème E

Analyse : Le problème consiste à calculer l'espérance du carré de la somme XOR d'un sous-ensemble d'éléments, où chaque élément \(a_i\) est inclus avec une probabilité \(p_i / 10000\). Nous utilisons la programmation dynamique. Soit \(dp[j]\) la probabilité que la somme XOR courante soit \(j\). Pour chaque élément, nous mettons à jour les probabilités en fonction de son inclusion ou non. Finalement, l'espérance est la somme de \(dp[j] \times j^2\). Les calculs se font modulo \(10^9+7\).

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

void solve() {
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    long long inv10000 = power(10000, MOD - 2);
    vector<long long> p(n);
    for (int i = 0; i < n; ++i) {
        long long prob;
        cin >> prob;
        p[i] = (prob * inv10000) % MOD;
    }
    
    vector<long long> dp(1024, 0);
    dp[0] = 1;
    
    for (int i = 0; i < n; ++i) {
        vector<long long> next_dp(1024, 0);
        long long prob_in = p[i];
        long long prob_out = (1 - prob_in + MOD) % MOD;
        
        for (int j = 0; j < 1024; ++j) {
            if (dp[j] == 0) continue;
            next_dp[j ^ a[i]] = (next_dp[j ^ a[i]] + dp[j] * prob_in) % MOD;
            next_dp[j] = (next_dp[j] + dp[j] * prob_out) % MOD;
        }
        dp = next_dp;
    }
    
    long long expected_value = 0;
    for (int j = 0; j < 1024; ++j) {
        long long term = (dp[j] * j) % MOD;
        term = (term * j) % MOD;
        expected_value = (expected_value + term) % MOD;
    }
    
    cout << expected_value << "\n";
}

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