Problème 1 : Vérification de parité

Ce problème consiste à déterminer si un entier est pair. Si l'entier est impair, on retourne -1 ; sinon, on le divise en deux parties égales.

#include <iostream>
using namespace std;

int main() {
    int valeur;
    cin >> valeur;
    if (valeur % 2 != 0) {
        cout << -1;
    } else {
        int moitie = valeur / 2;
        cout << moitie << " " << moitie;
    }
    return 0;
}

Problème 2 : Recherche par force brute

On cherche le nombre minimal d'opérations pour transformer un entier en carré parfait, en utilisant des additions ou soustractions de 2. L'idée est d'itérer sur des bases potentielles et vérifier la parité de la différence.

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

int main() {
    long long cible;
    cin >> cible;
    long long operationsMin = LLONG_MAX;
    for (long long base = 1; base <= 1000000; ++base) {
        long long carre = base * base;
        if (carre == cible) {
            operationsMin = 0;
            break;
        }
        long long diff = (cible > carre) ? (cible - carre) : (carre - cible);
        if (diff % 2 == 0) {
            operationsMin = min(operationsMin, diff / 2);
        }
    }
    cout << operationsMin;
    return 0;
}

Problème 3 : Utilisation de préfixes sommables

À partir d'une chaîne de caractères, on calcule le nombre minimal de changements pour que toutes les lettres majuscules soient à gauche et les minuscules à droite, en utilisant des cumuls préfixes et suffixes.

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;

int estMajuscule(char c) {
    return (c >= 'A' && c <= 'Z') ? 1 : 0;
}

int estMinuscule(char c) {
    return (c >= 'a' && c <= 'z') ? 1 : 0;
}

int main() {
    string texte;
    cin >> texte;
    int longueur = texte.size();
    int cumulMaj[longueur + 1] = {0}, cumulMin[longueur + 1] = {0};
    int suffMaj[longueur + 2] = {0}, suffMin[longueur + 2] = {0};

    for (int i = 1; i <= longueur; ++i) {
        cumulMaj[i] = cumulMaj[i - 1] + estMajuscule(texte[i - 1]);
        cumulMin[i] = cumulMin[i - 1] + estMinuscule(texte[i - 1]);
    }
    for (int i = longueur; i >= 1; --i) {
        suffMaj[i] = suffMaj[i + 1] + estMajuscule(texte[i - 1]);
        suffMin[i] = suffMin[i + 1] + estMinuscule(texte[i - 1]);
    }

    int resultat = INT_MAX;
    for (int i = 1; i < longueur; ++i) {
        resultat = min(resultat, cumulMin[i] + suffMaj[i + 1]);
    }
    cout << resultat;
    return 0;
}

Problème 4 : Technique des deux pointeurs

Dans une séquence d'entiers, on cherche le nombre de sous-séquences de longueur fixe qui contiennent tous les entiers d'un ensemble cible. Une fenêtre glissante avec un compteur de fréquences est utilisée.

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> sequence(n);
    for (int i = 0; i < n; ++i) {
        cin >> sequence[i];
    }

    vector<int> frequence(k + 1, 0);
    int manquants = k, compteur = 0;
    for (int i = 0; i < n; ++i) {
        int element = sequence[i];
        if (element <= k && frequence[element] == 0) {
            manquants--;
        }
        frequence[element]++;
        if (i >= k - 1) {
            if (i >= k) {
                int sortant = sequence[i - k];
                frequence[sortant]--;
                if (sortant <= k && frequence[sortant] == 0) {
                    manquants++;
                }
            }
            if (manquants == 0) {
                compteur++;
            }
        }
    }
    cout << compteur;
    return 0;
}

Problème 5 : Calcul avec des vecteurs en géométrie

Pour trouver l'aire maximale d'un parallélogramme formé par quatre points, on regroupe les segments par vceteurs directionnels et teste les combinaisons via le produit vectoriel.

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

typedef pair<long long, long long> Vecteur;

int main() {
    int n;
    cin >> n;
    vector<Vecteur> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].first >> points[i].second;
    }

    map<Vecteur, vector<pair<int, int>>> regroupement;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++n) {
            long long dx = points[j].first - points[i].first;
            long long dy = points[j].second - points[i].second;
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }
            regroupement[{dx, dy}].emplace_back(i, j);
        }
    }

    long long aireMax = 0;
    for (auto& paire : regroupement) {
        const Vecteur& direction = paire.first;
        const vector<pair<int, int>>& segments = paire.second;
        for (size_t i = 0; i < segments.size(); ++i) {
            for (size_t j = i + 1; j < segments.size(); ++j) {
                int idx1 = segments[i].first, idx2 = segments[j].first;
                Vecteur orthogonal = {
                    points[idx2].first - points[idx1].first,
                    points[idx2].second - points[idx1].second
                };
                long long aire = abs(direction.first * orthogonal.second - direction.second * orthogonal.first);
                aireMax = max(aireMax, aire);
            }
        }
    }

    if (aireMax == 0) {
        cout << -1;
    } else {
        cout << aireMax << ".0";
    }
    return 0;
}

Problème 6 : Tri et classement

À partir d'un ensemble de valeurs, on détermine le rang d'un élément spécifique après tri, en comptant les éléments précédents.

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

struct Element {
    int identifiant;
    int valeur;
};

bool comparaison(const Element& a, const Element& b) {
    if (a.valeur == b.valeur) return a.identifiant > b.identifiant;
    return a.valeur < b.valeur;
}

int main() {
    int cas;
    cin >> cas;
    while (cas--) {
        vector<Element> liste(5);
        for (int i = 0; i < 5; ++i) {
            cin >> liste[i].valeur;
            liste[i].identifiant = i + 1;
        }
        sort(liste.begin(), liste.end(), comparaison);
        int position = 0;
        for (int i = 0; i < 5; ++i) {
            if (liste[i].identifiant == 1) {
                position = i;
                break;
            }
        }
        cout << 4 - position << endl;
    }
    return 0;
}

Problème 7 : Théorie des jeux avec nombres premiers

On analyse une séquence de nombres pour prédire le gagnant d'un jeu basé sur la parité des comptes de nombres premiers, en traitant le cas spécial du nombre 3.

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

vector<int> estPremier(200001, 0);

void initialiser() {
    for (int i = 2; i <= 200000; ++i) {
        bool premier = true;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                premier = false;
                break;
            }
        }
        if (premier) estPremier[i] = 1;
    }
}

int main() {
    initialiser();
    int cas;
    cin >> cas;
    while (cas--) {
        int n;
        cin >> n;
        int comptePremiers = 0, compteTroi = 0;
        for (int i = 0; i < n; ++i) {
            int nombre;
            cin >> nombre;
            if (estPremier[nombre]) {
                comptePremiers++;
                if (nombre == 3) compteTroi++;
            }
        }
        if (comptePremiers == 0 || comptePremiers == compteTroi) {
            cout << -1 << endl;
        } else {
            int reste = comptePremiers - compteTroi;
            cout << (reste % 2 == 0 ? 1 : 0) << endl;
        }
    }
    return 0;
}

Problème 8 : Énumération et divisibilité

Pour un entier donné, on compte le nombre de façons de le représenter comme la somme d'un nombre à trois chiffres et de son inverse, en énumérant les chiffres extrêmes et en vérifiant la divisibilité par 11.

#include <iostream>
using namespace std;

int main() {
    int cas;
    cin >> cas;
    while (cas--) {
        long long cible;
        cin >> cible;
        int solutions = 0;
        for (int chiffreGauche = 1; chiffreGauche <= 9; ++chiffreGauche) {
            for (int chiffreDroit = 0; chiffreDroit <= 9; ++chiffreDroit) {
                for (long long puissance = 1; puissance <= 1e17; puissance *= 10) {
                    long long intermediaire = cible - chiffreGauche * puissance - chiffreDroit;
                    if (intermediaire >= 0 && intermediaire % 11 == 0) {
                        long long milieu = intermediaire / 11;
                        if (milieu < puissance) {
                            solutions++;
                        }
                    }
                }
            }
        }
        cout << solutions << endl;
    }
    return 0;
}