Problème A

La solution consiste à vérifier si la chaîne correspond au format attendu : la longueur doit être impaire, avec des '1' avant le '/', un '/' au milieu, et des '2' après.

#include <iostream>
#include <string>

using namespace std;

int main() {
    int longueur;
    string chaine;
    cin >> longueur >> chaine;
    bool valide = true;
    if (longueur % 2 == 0) valide = false;
    int milieu = (longueur + 1) / 2;
    for (int pos = 1; pos < milieu; pos++) {
        if (chaine[pos - 1] != '1') valide = false;
    }
    if (chaine[milieu - 1] != '/') valide = false;
    for (int pos = milieu + 1; pos <= longueur; pos++) {
        if (chaine[pos - 1] != '2') valide = false;
    }
    if (valide) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Problème B

Il faut vérifier que chaque caractère apparaît exactement deux fois et que les paires consécutives sont identiques, avec une longueur paire.

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    string texte;
    cin >> texte;
    int taille = texte.size();
    bool conforme = true;
    if (taille % 2 != 0) conforme = false;
    for (int idx = 0; idx < taille; idx += 2) {
        if (texte[idx] != texte[idx + 1]) conforme = false;
    }
    map<char, int> compteur;
    for (char c : texte) compteur[c]++;
    for (auto& paire : compteur) {
        if (paire.second != 2) conforme = false;
    }
    if (conforme) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Problème C

Pour chaque position '/', on cherche la plus longue séquence symétrique de '1' à gauche et '2' à droite.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int longueur;
    string sequence;
    cin >> longueur >> sequence;
    sequence = "0" + sequence; // Décalage pour indexation
    int resultat = 0;
    for (int idx = 1; idx <= longueur; idx++) {
        if (sequence[idx] == '/') {
            int rayon = 0;
            while (idx - rayon - 1 >= 1 && idx + rayon + 1 <= longueur 
                   && sequence[idx - rayon - 1] == '1' && sequence[idx + rayon + 1] == '2') {
                rayon++;
            }
            resultat = max(resultat, 1 + 2 * rayon);
        }
    }
    cout << resultat << "\n";
    return 0;
}

Problème D

L'approche utilise des pointeurs pour parcourir l'array compressé en valeurs et comptes, en gérant les cas selon les fréquences des éléments.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> donnees(n);
    for (int i = 0; i < n; i++) cin >> donnees[i];
    vector<int> valeurs, comptes;
    for (int i = 0; i < n; i++) {
        if (valeurs.empty() || donnees[i] != valeurs.back()) {
            valeurs.push_back(donnees[i]);
            comptes.push_back(1);
        } else {
            comptes.back()++;
        }
    }
    int m = valeurs.size();
    vector<int> marque(m, 0);
    int gauche = 0, reponse = 0;
    for (int droite = 0; droite < m; droite++) {
        if (comptes[droite] < 2) {
            while (gauche <= droite) {
                marque[valeurs[gauche]] = 0;
                gauche++;
            }
        } else if (comptes[droite] > 2) {
            if (!marque[valeurs[droite]]) {
                reponse = max(reponse, 2 * (droite - gauche + 1));
            }
            while (gauche < droite) {
                marque[valeurs[gauche]] = 0;
                gauche++;
            }
            marque[valeurs[droite]] = 1;
        } else {
            while (gauche <= droite && marque[valeurs[droite]]) {
                marque[valeurs[gauche]] = 0;
                gauche++;
            }
            marque[valeurs[droite]] = 1;
        }
        if (gauche <= droite) {
            reponse = max(reponse, 2 * (droite - gauche + 1));
        }
    }
    cout << reponse << "\n";
    return 0;
}

Problème E

On utilise des tableaux préfixes pour les '1', '2', et '/', puis une rechecrhe binaire pour optimiser la recherche des '/' dans un intervalle.

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

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = "0" + s; // Indexation à partir de 1
    vector<int> prefix1(n + 1, 0), prefix2(n + 1, 0), prefixSlash(n + 1, 0);
    vector<int> positionsSlash;
    for (int i = 1; i <= n; i++) {
        prefix1[i] = prefix1[i - 1] + (s[i] == '1');
        prefix2[i] = prefix2[i - 1] + (s[i] == '2');
        prefixSlash[i] = prefixSlash[i - 1] + (s[i] == '/');
        if (s[i] == '/') positionsSlash.push_back(i);
    }
    for (int query = 0; query < q; query++) {
        int l, r;
        cin >> l >> r;
        int debut = lower_bound(positionsSlash.begin(), positionsSlash.end(), l) - positionsSlash.begin();
        int fin = upper_bound(positionsSlash.begin(), positionsSlash.end(), r) - positionsSlash.begin() - 1;
        int maxLongueur = 0;
        while (debut <= fin) {
            int milieu = (debut + fin) / 2;
            int pos = positionsSlash[milieu];
            int cnt1 = prefix1[pos - 1] - prefix1[l - 1];
            int cnt2 = prefix2[r] - prefix2[pos];
            int longueur = 2 * min(cnt1, cnt2) + 1;
            maxLongueur = max(maxLongueur, longueur);
            if (cnt1 < cnt2) {
                debut = milieu + 1;
            } else if (cnt1 > cnt2) {
                fin = milieu - 1;
            } else {
                break;
            }
        }
        cout << maxLongueur << "\n";
    }
    return 0;
}

Problème F

Une approche par DP bitmask pour trouver la plus longue sous-séquence où chaque élément apparaît exactement deux fois.

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

using namespace std;

const int MAX_VAL = 20;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    // Prétraitement des prochaines occurrences
    vector<vector<int>> prochain(n + 2, vector<int>(MAX_VAL, n + 1));
    for (int i = n - 1; i >= 0; i--) {
        for (int v = 0; v < MAX_VAL; v++) {
            prochain[i][v] = prochain[i + 1][v];
        }
        prochain[i][a[i] - 1] = i + 1; // a[i] est 1-indexé dans l'exemple
    }
    int totalMasks = 1 << MAX_VAL;
    vector<int> dp(totalMasks, n + 1);
    dp[0] = 0;
    int resultat = 0;
    for (int mask = 0; mask < totalMasks; mask++) {
        int compteur = 0;
        for (int bit = 0; bit < MAX_VAL; bit++) {
            if (mask & (1 << bit)) {
                compteur += 2;
                int precedent = mask ^ (1 << bit);
                int pos1 = dp[precedent];
                int pos2 = prochain[pos1][bit];
                dp[mask] = min(dp[mask], prochain[pos2][bit]);
            }
        }
        if (dp[mask] <= n) resultat = max(resultat, compteur);
    }
    cout << resultat << "\n";
    return 0;
}