A. Validation d'une chaîne « red »

L'objectif est de vérifier si une chaîne de caractères donnée se compose exclusivement des lettres 'r', 'e' et 'd'. Une approche par énumération directe de chaque caractère suffit.

#include <iostream>
#include <string>

using namespace std;

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

    string input;
    cin >> input;

    bool isValid = true;
    size_t index = 0;
    while (index < input.length()) {
        char ch = input[index];
        if (ch != 'r' && ch != 'e' && ch != 'd') {
            isValid = false;
            break;
        }
        ++index;
    }

    cout << (isValid ? "Yes" : "No") << endl;
    return 0;
}

B. Construction de matrice conditionnelle

On doit construire une matrice dont les deux premiers éléments sont différents, sous des contraintes de dimensions. La solution n'existe que pour une matrice ayant une seule ligne ou une seule colonne, en dehors du cas trivial 1×1.

#include <iostream>

using namespace std;

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

    int rowCount, colCount;
    cin >> rowCount >> colCount;

    if ((rowCount != 1 && colCount != 1) || (rowCount == 1 && colCount == 1)) {
        cout << -1 << endl;
        return 0;
    }

    if (rowCount == 1) {
        cout << "10";
        for (int j = 2; j < colCount; ++j) {
            cout << "0";
        }
        cout << endl;
    } else {
        cout << "1" << endl;
        for (int i = 1; i < rowCount; ++i) {
            cout << "0" << endl;
        }
    }

    return 0;
}

C. Comparaison entre pile et file

À partir d'une séquence d'opérations (ajout/retrait), on simule les comportements d'une pile et d'une file. On compare ensuite les séquences retirées avec une cible donnée pour identifier si le comportement correspond à une pile, une file, les deux, ou aucun.

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

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

    int seqLen, opCount;
    cin >> seqLen >> opCount;

    vector<int> target(seqLen);
    for (int i = 0; i < seqLen; ++i) {
        cin >> target[i];
    }

    stack<int> stackContainer;
    queue<int> queueContainer;
    vector<int> stackSequence, queueSequence;

    for (int i = 0; i < opCount; ++i) {
        int opType;
        cin >> opType;
        if (opType == 1) {
            int value;
            cin >> value;
            stackContainer.push(value);
            queueContainer.push(value);
        } else {
            int stackTop = stackContainer.top();
            int queueFront = queueContainer.front();
            stackContainer.pop();
            queueContainer.pop();
            stackSequence.push_back(stackTop);
            queueSequence.push_back(queueFront);
        }
    }

    bool stackValid = true, queueValid = true;
    for (int i = 0; i < seqLen; ++i) {
        if (stackSequence[i] != target[i]) {
            stackValid = false;
            break;
        }
    }
    for (int i = 0; i < seqLen; ++i) {
        if (queueSequence[i] != target[i]) {
            queueValid = false;
            break;
        }
    }

    if (!stackValid && !queueValid) {
        cout << -1 << endl;
    } else if (stackValid && queueValid) {
        cout << "both" << endl;
    } else if (stackValid) {
        cout << "stack" << endl;
    } else {
        cout << "queue" << endl;
    }

    return 0;
}

D. Nombre de chaînes partielles via union-find

Les contraintes d'égalité entre positions définissent des composantes connexes. Le nombre total de chaînes partielles égale 26 puissance le nombre de composantes, calculé modulo 998244353 avec une exponentiation rapide.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

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

vector<int> parentSet;

int findRoot(int x) {
    if (parentSet[x] == x) {
        return x;
    }
    return parentSet[x] = findRoot(parentSet[x]);
}

void uniteSets(int a, int b) {
    int rootA = findRoot(a);
    int rootB = findRoot(b);
    if (rootA != rootB) {
        parentSet[rootB] = rootA;
    }
}

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

    int n, k;
    cin >> n >> k;

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

    for (int i = 0; i < k; ++i) {
        int u, v;
        cin >> u >> v;
        uniteSets(u, v);
    }

    int componentCount = 0;
    for (int i = 1; i <= n; ++i) {
        if (parentSet[i] == i) {
            componentCount++;
        }
    }

    long long answer = fastPower(26, componentCount) % MOD;
    cout << answer << endl;

    return 0;
}

E. Couverture minimale de sommets dans un arbre

Pour obtenir des composantes connexes de taille 1, il faut supprimer un ensemble de sommets tel qu'il ne reste aucune arête, ce qui corrrespond à la couverture minimale de sommets. On utilise une programmation dynamique sur l'arbre pour calculer le nombre minimal de suppressions pour chaque sous-arbre.

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

using namespace std;

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

    int numNodes;
    cin >> numNodes;

    vector<vector<int>> adjacency(numNodes + 1);
    for (int i = 0; i < numNodes - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adjacency[u].push_back(v);
        adjacency[v].push_back(u);
    }

    vector<array<int, 2>> dp(numNodes + 1);

    function<void(int, int)> dfs = [&](int node, int parent) {
        dp[node][0] = 0;
        dp[node][1] = 1;
        for (int child : adjacency[node]) {
            if (child == parent) continue;
            dfs(child, node);
            dp[node][0] += dp[child][1];
            dp[node][1] += min(dp[child][0], dp[child][1]);
        }
    };

    dfs(1, 0);

    for (int i = 1; i <= numNodes; ++i) {
        cout << min(dp[i][0], dp[i][1]) << endl;
    }

    return 0;
}

F. Coloration de graphe fonctionnel

On modélise le problème comme une coloration de graphe où chaque nœud a un unique successeur. Le graphe se décompose en composantes connexes contenant un cycle avec des arbres greffés. On calcule d'abord les contributions des nœuds non cycliques (25 posibilités chacun), puis on applique la formule de coloration de cycle pour chaque cycle détecté par suppression topologique des nœuds d'entrée nulle.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MOD = 998244353;

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

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

    int n;
    cin >> n;

    vector<int> nextNode(n + 1), inDeg(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> nextNode[i];
        inDeg[nextNode[i]]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
    }

    int nonCycleCount = 0;
    vector<bool> removed(n + 1, false);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        removed[cur] = true;
        nonCycleCount++;
        int nxt = nextNode[cur];
        inDeg[nxt]--;
        if (inDeg[nxt] == 0) {
            q.push(nxt);
        }
    }

    long long result = fastPower(25, nonCycleCount);

    vector<bool> visited(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (removed[i] || visited[i]) {
            continue;
        }

        int cycleLen = 0;
        int current = i;
        while (!visited[current]) {
            visited[current] = true;
            cycleLen++;
            current = nextNode[current];
        }

        long long cycleWays = fastPower(25, cycleLen);
        if (cycleLen % 2 == 1) {
            cycleWays = (cycleWays - 25 + MOD) % MOD;
        } else {
            cycleWays = (cycleWays + 25) % MOD;
        }
        result = (result * cycleWays) % MOD;
    }

    cout << result << endl;

    return 0;
}