Problème C

La solution consiste à marquer les cellules qui ne peuvent pas être utilisées, puis à soustraire ce nombre du nombre total de cellules.

On utilise une structure de type map pour stocker les cellules déjà traitées afin d'éviter les doublons.

Code de la solution

#include<bits/stdc++.h>

#define int long long

using namespace std;

int grille, obstacle;
int resultat;

int depX[] = {0, 1, 2, -1, -2, 1, 2, -1, -2};
int depY[] = {0, 2, 1, -2, -1, -2, -1, 2, 1};

map<int, map<int, int>> historique;

int main(){
    
    cin >> grille >> obstacle;
    resultat = grille * grille;
    
    for(int i = 1; i <= obstacle; ++i){
        int x, y;
        cin >> x >> y;
        
        for(int dir = 0; dir <= 8; ++dir){
            int nx = x + depX[dir];
            int ny = y + depY[dir];
            
            if(nx < 1 || nx > grille || ny < 1 || ny > grille) continue;
            
            if(!historique[nx][ny]){
                historique[nx][ny] = 1;
                resultat--;
            }
        }
    }
    
    cout << resultat;
    return 0;
}

Problème D

Pour ce problème, il faut procéder à l'envers. On calcule d'abord le nombre total de combinaisons psosibles, puis on soustrait celles qui ne respectent pas les contraintes.

Le nombre total se calcule en choisissant deux points comme extrémités gauche et droite, puis en ajoutant un troisième point.

Une combinaison est invalide si elle contient un intervalle interdit. Avec un seul intervalle, le calcul est simple : on multiplie le nombre de points à gauche de l'intervalle par le nombre de points à droite. Avec plusieurs intervalles, le problème de chevauchement apparaît.

Pour résoudre ce problème de doublons, on固定e une extrémité droite. Pour chaque extrémité droite, on détermine la plus grande extrémité gauche qui rend l'intervalle invalide. Si l'nitervalle [l, r] est invalide, alors [l-1, r] l'est aussi car il contient l'intervalle interdit.

Ainsi, pour chaque position, on conserve le maximum des extrémités gauches invalides. Si le côté droit d'un intervalle interdit coincide avec la position actuelle, on prend le maximum des extrémités gauches. Si le côté droit est antérieur, on prend le maximum de toutes les positions précédentes.

Code de la solution

#include<bits/stdc++.h>

#define int long long

using namespace std;

int taille, nbIntervalles;
int tableau[200005];
int gauche[200005], droite[200005];
int reponse;

int main(){
    
    cin >> taille >> nbIntervalles;
    reponse = nbIntervalles * (nbIntervalles - 1) / 2 + nbIntervalles;
    
    for(int i = 1; i <= nbIntervalles; ++i){
        cin >> gauche[i] >> droite[i];
        tableau[droite[i]] = max(tableau[droite[i]], gauche[i]);
    }
    
    for(int i = 1; i <= nbIntervalles; ++i){
        tableau[i] = max(tableau[i-1], tableau[i]);
        reponse -= tableau[i];
    }
    
    cout << reponse;
    return 0;
}

Problème E

Selon la logique habituelle, nous devons faire i → p_i. Ensuite, que doit-on faire ?