A. Repas de Cidoai

Approche : Le problème consiste à appliquer une logique conditionnelle basée sur la valeur de n pour itérer sur des coûts spécifiques. On simule le processus de soustraction jusqu'à ce que la condition ne soit plus satisfaite.

Code AC :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e6 + 10;
const ll INF = 0x3f3f3f3f3f3f;

ll total, prix1, prix2, prix3;

ll obtenir_prix(ll reste) {
    if (reste >= prix1) return prix1;
    if (reste >= prix2) return prix2;
    if (reste >= prix3) return prix3;
    return -1;
}

void resoudre() {
    cin >> total >> prix1 >> prix2 >> prix3;
    ll compteur = 0;
    ll courant = obtenir_prix(total);
    while (courant != -1) {
        total -= courant;
        compteur++;
        courant = obtenir_prix(total);
    }
    cout << compteur << endl;
}

void optimiser_entree_sortie() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    optimiser_entree_sortie();
    ll cas_test = 1;
    // cin >> cas_test;
    while (cas_test--) resoudre();
    return 0;
}

B. Écoute musicale de Cidoai

Approche : La séquence décrite suit un motif de croissacne puis décroissance. En analysant les valeurs extrêmes (maximum et minimum), on déduit que la réponse dépend de la longueur du pas entre ces valeurs. La discussion se base sur la parité de cette longueur pour calculer les paramètres.

Code AC :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e6 + 10;
const ll INF = 0x3f3f3f3f3f3f;

void resoudre() {
    int n;
    cin >> n;
    ll valeur_max = 0, valeur_min = INT_MAX;
    for (int i = 0; i < n; i++) {
        ll num;
        cin >> num;
        valeur_max = max(valeur_max, num);
        valeur_min = min(valeur_min, num);
    }
    ll param_a, param_b;
    ll somme = valeur_max + valeur_min;
    longueur = valeur_max - valeur_min + 1;
    if (longueur % 2 == 1) {
        param_b = somme / 2;
        param_a = (valeur_max - valeur_min) * 2 / 2;
    } else {
        param_b = somme / 2 + 1;
        param_a = 2 * ((longueur / 2) - 1) + 1;
    }
    cout << param_a << ' ' << param_b << endl;
}

void optimiser_entree_sortie() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    optimiser_entree_sortie();
    ll cas_test = 1;
    // cin >> cas_test;
    while (cas_test--) resoudre();
    return 0;
}

C. Plantes de Cidoai

Approche : L'entrée est générée aléatoirement selon des règles données. On simule cette génération pour obtenir les opérations 1 et 2. Pour l'opération 1, on place des éléments dans les espaces vides, en maintanant une liste des positions libres par colonne. L'opération 2 supprime des éléments si possible.

Code AC :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e6 + 10;
const ll INF = 0x3f3f3f3f3f3f;

unsigned graine;
unsigned generer_aleatoire() {
    unsigned resultat = graine;
    graine ^= graine << 13;
    graine ^= graine >> 17;
    graine ^= graine << 5;
    return resultat;
}

int matrice[20010][210];
vector<int> colonnes[210];

void resoudre() {
    int lignes, colonnes_n, operations;
    cin >> lignes >> colonnes_n >> operations >> graine;
    for (int j = 1; j <= colonnes_n; j++) {
        colonnes[j].clear();
        for (int i = 1; i <= lignes; i++) {
            colonnes[j].push_back(i);
        }
    }
    for (int op = 0; op < operations; op++) {
        int type = (generer_aleatoire() % 2) + 1;
        if (type == 1) {
            int col = (generer_aleatoire() % colonnes_n) + 1;
            int valeur = (generer_aleatoire() % (lignes * colonnes_n)) + 1;
            for (auto &ligne : colonnes[col]) {
                matrice[ligne][col] = valeur;
            }
            colonnes[col].clear();
        } else {
            int ligne = (generer_aleatoire() % lignes) + 1;
            int col = (generer_aleatoire() % colonnes_n) + 1;
            if (matrice[ligne][col] != 0) {
                matrice[ligne][col] = 0;
                colonnes[col].push_back(ligne);
            }
        }
    }
    ll resultat = 0;
    for (int i = 1; i <= lignes; i++) {
        for (int j = 1; j <= colonnes_n; j++) {
            resultat ^= (matrice[i][j] * ((i - 1) * colonnes_n + j));
        }
    }
    cout << resultat << endl;
}

void optimiser_entree_sortie() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    optimiser_entree_sortie();
    ll cas_test = 1;
    // cin >> cas_test;
    while (cas_test--) resoudre();
    return 0;
}

D. Chats de Cidoai

Approche : Après reformulation, le problème implique d'ajouter des suites arithmétiques à un intervalle. On utilise une différence d'ordre deux pour gérer ces ajouts efficacement, suivis de deux passes de calcul de sommes préfixes pour obtenir le tableau final.

Code AC :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 6e6 + 10; // Taille importante selon l'énoncé
const ll INF = 0x3f3f3f3f3f3f;

ll tableau[MAX_N];

void ajouter_suite(ll arr[], int gauche, int droite, ll premier, ll difference) {
    arr[gauche] += premier;
    arr[gauche + 1] += difference - premier;
    arr[droite + 1] -= (droite - gauche + 1) * difference + premier;
    arr[droite + 2] -= (gauche - droite) * difference - premier;
}

void calculer_sommes_prefixes(ll arr[], int taille) {
    for (int i = 1; i <= taille; i++) arr[i] += arr[i - 1];
    for (int i = 1; i <= taille; i++) arr[i] += arr[i - 1];
}

void resoudre() {
    int n;
    cin >> n;
    string sequence;
    cin >> sequence;
    int compteur = 1;
    for (size_t i = 0; i + 1 < sequence.size(); i++) {
        if (sequence[i + 1] == sequence[i]) {
            compteur++;
        } else {
            int val = compteur - 1;
            ajouter_suite(tableau, 1, compteur, val, -1);
            compteur = 1;
        }
    }
    if (!sequence.empty() && sequence.back() == sequence[sequence.size() - 2]) {
        int val = compteur - 1;
        ajouter_suite(tableau, 1, compteur, val, -1);
    } else {
        ajouter_suite(tableau, 1, 1, 0, -1);
    }
    calculer_sommes_prefixes(tableau, n);
    ll resultat = 0;
    for (int i = 1; i <= n; i++) {
        resultat ^= (i * (n - tableau[i]));
    }
    cout << resultat << endl;
}

void optimiser_entree_sortie() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    optimiser_entree_sortie();
    ll cas_test = 1;
    // cin >> cas_test;
    while (cas_test--) resoudre();
    return 0;
}

E. Cola de Cidoai

Approche : Le problème concerne la construction d'un arbre couvrant de poids minimal avec des contraintes de degré. On identifie que pour minimiser le poids total, il faut prioriser les nœuds avec la plus petite valeur, en utilisant leur degré disponible. Une approche gloutonne trie les nœuds par valeur croissante et, à égalité, par degré décroissant, puis alloue les arêtes jusqu'à atteindre n-1.

Code AC :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e6 + 10;
const ll INF = 0x3f3f3f3f3f3f;

struct Noeud {
    ll valeur;
    int degre;
};

void resoudre() {
    int n;
    cin >> n;
    vector<Noeud> noeuds(n);
    for (int i = 0; i < n; i++) cin >> noeuds[i].valeur;
    for (int i = 0; i < n; i++) cin >> noeuds[i].degre;
    sort(noeuds.begin(), noeuds.end(), [](const Noeud &a, const Noeud &b) {
        if (a.valeur == b.valeur) return a.degre > b.degre;
        return a.valeur < b.valeur;
    });
    ll poids_total = 0;
    int aretes_restantes = n - 1;
    for (auto &noeud : noeuds) {
        int aretes_utilisees = min(noeud.degre, aretes_restantes);
        poids_total += noeud.valeur * aretes_utilisees;
        aretes_restantes -= aretes_utilisees;
        if (aretes_restantes <= 0) break;
    }
    cout << poids_total << endl;
}

void optimiser_entree_sortie() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    optimiser_entree_sortie();
    ll cas_test = 1;
    // cin >> cas_test;
    while (cas_test--) resoudre();
    return 0;
}