A - Plante Exponentielle

Ce problème décrit une plante dont la hauteur augmente de manière exponentielle chaque jour. Initialement, la hauteur est de 1. Chaque jour, la plante double sa hauteur cumulée jusqu'à présent. Nous devons déterminer le nombre minimal de jours nécessaires pour que la plante atteigne ou dépasse une hauteur cible spécifiée.

La hauteur de la plante au jour k est la somme des hauteurs ajoutées chaque jour, soit \(2^0 + 2^1 + \dots + 2^{k-1}\). Cette somme est égale à \(2^k - 1\). Nous cherchons le plus petit k tel que \(2^k - 1 \geq N\). Une approche directe consiste à simuler la croissance jour par jour.

#include <iostream>

// Utilisation explicite des types pour éviter 'using namespace std;'
// Pour des concours, 'using namespace std;' est souvent toléré pour la concision.

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); // Optimisations d'entrée/sortie

    int hauteurCible;
    std::cin >> hauteurCible;

    int joursPasses = 0;
    long long hauteurActuelle = 0; // Utiliser long long pour éviter le débordement si N est grand

    // La hauteur initiale au jour 0 est 1 (2^0).
    // Le jour 0 on ajoute 2^0, le jour 1 on ajoute 2^1, etc.
    // La boucle compte le nombre de "jours" ou d'étapes de croissance.
    while (hauteurActuelle <= hauteurCible) {
        hauteurActuelle += (1LL << joursPasses); // Ajoute 2^joursPasses à la hauteur cumulée
        joursPasses++;
    }

    std::cout << joursPasses << "\n";

    return 0;
}

B - AtCoder Janken 2

Dans ce problème, nous avons N participants, chacun avec un nom (une chaîne de caractères) et un score (un entier). Nous devons d'abord calculer la somme totale de tous les scores. Ensuite, nous prenons cette somme modulo N. Ce résultat sera l'indice (base zéro) du participant dont le nom doit être affiché. Avant d'obtenir le nom, tous les noms des participants doivent être triés par ordre lexicographique croissant.

Il est important de noter que nous n'avons pas besoin de stocker les noms et les scores ensemble dans une structure comme std::pair ou une classe. Les scores ne servent qu'à calculer la somme totale. Les noms sont stockés séparément pour le tri.

#include <iostream>
#include <vector>
#include <string>
#include <numeric> // Pour std::accumulate si on ne somme pas directement

// Utilisation explicite des types pour éviter 'using namespace std;'

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); // Optimisations d'entrée/sortie

    int nombreParticipants;
    std::cin >> nombreParticipants;

    std::vector<std::string> nomsParticipants(nombreParticipants);
    long long sommeScoresTotale = 0; // Utiliser long long pour la somme des scores

    for (int i = 0; i < nombreParticipants; ++i) {
        std::cin >> nomsParticipants[i];
        int scoreActuel;
        std::cin >> scoreActuel;
        sommeScoresTotale += scoreActuel;
    }

    // Calcul de l'indice cible après le tri
    int indiceCible = sommeScoresTotale % nombreParticipants;

    // Tri des noms par ordre lexicographique
    std::sort(nomsParticipants.begin(), nomsParticipants.end());

    // Affichage du nom correspondant à l'indice cible
    std::cout << nomsParticipants[indiceCible] << "\n";

    return 0;
}

C - AtCoder Magics

Nous avons N cartes, chacune caractérisée par une valeur d'attaque A et un coût C. Une carte est considérée comme "utile" et doit être conservée si elle n'est pas dominée par une autre carte. Une carte X est dominée par une carte Y si Y a une valeur d'attaque supérieure ou égale à X (A_Y >= A_X) ET un coût inférieur à X (C_Y < C_X). L'objectif est de trouver les indices originaux des cartes utiles.

Approche Naïve (inefficace)

Une approche brute consisterait à itérer sur chaque carte i et, pour chacune d'elles, vérifier toutes les autres cartes j pour voir si i est dominée. Si A_j >= A_i et C_j < C_i, alors la carte i est dominée. Cette vérification prendrait \(O(N^2)\) temps, ce qui est trop lent pour \(N) jusqu'à \(2 \cdot 10^5\).

Approche Optimisée (balayage et minimum suffixe/préfixe)

Pour optimiser, nous pouvons utiliser le tri et une observation clé. Si nous trions les cartes d'une certaine manière, la condition de domination peut être vérifiée plus efficacement.

L'idée est de trier les cartes par leur valeur d'attaque A dans l'ordre décroissant. Si deux cartes ont la même valeur A, l'ordre de tri entre elles n'a pas d'importance pour la logique de domination, mais on peut les trier par C croissant pour une certaine cohérence.

Une fois les cartes triées par A décroissant, nous parcourons cette liste. Nous maintenons un minimum de coût C vu jusqu'à présent (initialisé à une très grande valeur). Pour chaque carte que nous rencontrons:

• Si le coût C de la carte actuelle est inférieur au minimum de coût C enregistré jusqu'à présent (parmi toutes les cartes avec une attaque A supérieure ou égale que nous avons déjà traitées), alors cette carte n'est dominée par aucune des cartes précédentes (qui avaient des A plus grands ou égaux). De plus, elle pourrait potentiellement dominer des cartes futures (avec des A plus petits ou égaux). Nous conservons cette carte et mettons à jour notre minimum de coût C avec le coût de cette carte.
• Sinon, si le coût C de la carte actuelle est supérieur ou égal au minimum de coût C enregistré, cela signifie qu'il existe déjà une carte précédemment traitée (donc avec un A supérieur ou égal) qui a un coût inférieur ou égal. Dans ce cas, la carte actuelle est dominée (ou au moins pas "meilleure" en termes de coût pour une attaque donnée) et nous la rejetons.

Cette approche prend \(O(N \log N)\) pour le tri et \(O(N)\) pour le baalyage, ce qui est efficace.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Pour std::sort
#include <numeric>   // Pour std::iota

// Définition d'une grande valeur pour l'initialisation du minimum de coût
const int COUT_MAX_INITIAL = 1e9 + 7; 

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

    int nombreCartes;
    std::cin >> nombreCartes;

    std::vector<int> attaques(nombreCartes);
    std::vector<int> couts(nombreCartes);
    for (int i = 0; i < nombreCartes; ++i) {
        std::cin >> attaques[i] >> couts[i];
    }

    // Création d'un vecteur d'indices originaux [0, 1, ..., nombreCartes-1]
    std::vector<int> indicesOriginaux(nombreCartes);
    std::iota(indicesOriginaux.begin(), indicesOriginaux.end(), 0);

    // Tri des indices en fonction des valeurs d'attaque A (décroissant)
    // Si A est égal, on peut trier par C croissant, mais ce n'est pas strictement nécessaire pour la logique du min C.
    std::sort(indicesOriginaux.begin(), indicesOriginaux.end(),
              [&](int idx1, int idx2) {
                  if (attaques[idx1] != attaques[idx2]) {
                      return attaques[idx1] > attaques[idx2]; // Tri par A décroissant
                  }
                  return couts[idx1] < couts[idx2]; // Si A égal, tri par C croissant
              });

    int minCoutEncountered = COUT_MAX_INITIAL;
    std::vector<int> cartesUtilesIndices;

    // Parcours des cartes triées
    for (int originalIdx : indicesOriginaux) {
        if (couts[originalIdx] < minCoutEncountered) {
            // Cette carte est utile car son coût est inférieur au minimum vu jusqu'à présent
            // parmi les cartes avec une attaque supérieure ou égale.
            minCoutEncountered = couts[originalIdx];
            cartesUtilesIndices.push_back(originalIdx + 1); // Stocke l'indice 1-basé
        }
    }

    // Les indices des cartes utiles doivent être triés par leur valeur originale
    std::sort(cartesUtilesIndices.begin(), cartesUtilesIndices.end());

    std::cout << cartesUtilesIndices.size() << "\n";
    for (size_t i = 0; i < cartesUtilesIndices.size(); ++i) {
        std::cout << cartesUtilesIndices[i] << (i == cartesUtilesIndices.size() - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}

D - Papier Peint AtCoder

Ce problème nous demande de calculer la somme des "valeurs" d'un motif complexe dans une région rectangulaire donnée. Le motif est périodique et se répète sur une grille. La valeur de chaque cellule de la grille dépend de ses coordonnées modulo certaines périodes.

Le motif fondamental se répète horizontalement toutes les 4 unités et verticalement toutes les 2 unités. Les valeurs des cellules (x, y) peuvent être représentées par une petite matrice valeursMotif[x % 4][y % 2].

Les valeurs fournies dans l'énoncé sont: v[0][0]=2, v[0][1]=1``v[1][0]=1, v[1][1]=2``v[2][0]=0, v[2][1]=1``v[3][0]=1, v[3][1]=0Ce qui forme la matrice des motifs:

2 1
1 2
0 1
1 0

Pour calculer la somme des valeurs dans un rectangle [x_start, x_end-1] par [y_start, y_end-1], nous pouvons utiliser le principe d'inclusion-exclusion. Nous définirons une fonction utilitaire calculerSommePrefixe(x_max_exclusif, y_max_exclusif) qui retourne la somme des valeurs dans le rectangle [0, x_max_exclusif-1] par [0, y_max_exclusif-1]. Ensuite, la somme pour le rectangle désiré sera: calculerSommePrefixe(x_end, y_end) - calculerSommePrefixe(x_start, y_end) - calculerSommePrefixe(x_end, y_start) + calculerSommePrefixe(x_start, y_start).

La fonction calculerSommePrefixe(num_lignes, num_colonnes) itère sur toutes les combinaisons possibles de (x % 4, y % 2). Pour chaque combinaison (i, j), elle calcule combien de fois cette position de motif apparaît dans le rectangle de taille num_lignes x num_colonnes. Le nombre d'occurrences de x % P == offset dans un intervalle [0, L-1] est (L - offset + P - 1) / P (division entière).

#include <iostream>
#include <vector>

// Matrice des valeurs du motif, où valeursMotif[i][j] correspond à (x % 4, y % 2)
constexpr int valeursMotif[4][2] = {
    {2, 1}, // Pour x%4=0
    {1, 2}, // For x%4=1
    {0, 1}, // For x%4=2
    {1, 0}  // For x%4=3
};

// Fonction pour calculer la somme des valeurs dans un rectangle
// des coordonnées (0,0) inclusives jusqu'à (numLignes-1, numColonnes-1) inclusives.
// Autrement dit, pour un rectangle de dimensions numLignes x numColonnes.
long long calculerSommePrefixe(int numLignes, int numColonnes) {
    if (numLignes <= 0 || numColonnes <= 0) {
        return 0; // Aucun rectangle, somme nulle
    }

    long long sommeTotale = 0;
    
    // Parcourt les 4 possibilités de modulo 4 pour l'axe X (lignes)
    for (int i = 0; i < 4; ++i) {
        // Parcourt les 2 possibilités de modulo 2 pour l'axe Y (colonnes)
        for (int j = 0; j < 2; ++j) {
            // Calcule le nombre de fois où le motif (i, j) apparaît dans le rectangle.
            // La formule (Longueur - offset + Période - 1) / Période
            // calcule le nombre d'éléments x dans [0, Longueur-1] tels que x % Période == offset.
            // Ici, Longueur = numLignes pour l'axe X, et Période = 4.
            // Longueur = numColonnes pour l'axe Y, et Période = 2.
            long long countX = (numLignes - i + 4 - 1) / 4;
            long long countY = (numColonnes - j + 2 - 1) / 2;
            
            // Ajoute la contribution de cette cellule de motif à la somme totale
            sommeTotale += (long long)valeursMotif[i][j] * countX * countY;
        }
    }
    return sommeTotale;
}

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

    int xDebut, yDebut, xFin, yFin;
    std::cin >> xDebut >> yDebut >> xFin >> yFin;

    // Applique le principe d'inclusion-exclusion pour trouver la somme dans le rectangle [xDebut, xFin-1] x [yDebut, yFin-1].
    // Note: les coordonnées d'entrée sont souvent interprétées comme [A, B) et [C, D) dans le contexte de fonctions de somme préfixe.
    // L'expression `solve(C, D) - solve(C, B) - solve(A, D) + solve(A, B)` est correcte pour
    // un rectangle couvrant [A, C-1] en X et [B, D-1] en Y.
    long long resultat = calculerSommePrefixe(xFin, yFin) - 
                         calculerSommePrefixe(xDebut, yFin) - 
                         calculerSommePrefixe(xFin, yDebut) + 
                         calculerSommePrefixe(xDebut, yDebut);

    std::cout << resultat << "\n";

    return 0;
}