Problème 1 : Jeu de Nombres et Programmation Dynamique

Ce problème modélise un jeu séquentiel impliquant N entités disposées en cercle. Chaque entité annonce un entier dans l'intervalle [x+1, x+K], où x est le nombre précédent, sans dépasser une limite maximale M. L'entité qui annonce M perd. L'objectif est de déterminer, pour chaque position de départ, quelle catégorie d'entité remporte la partie en jouant de manière optimale.

La résolution repose sur la programmation dynamique. On définit un état indiquant si l'entité à une position donnée peut forcer une victoire lorsque le nombre actuel est j. Pour optimiser les transitions et éviter une complexité temporelle excessive, une somme suffixe est maintenue sur les états gagnants, réduisant ainsi la complexité de chaque transition à O(1).

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n_animals, max_num, step_limit;
    if (!(cin >> n_animals >> max_num >> step_limit)) return 0;
    
    vector<int> species(n_animals + 1);
    for (int i = 1; i <= n_animals; ++i) cin >> species[i];
    
    vector<int> extended_species(2 * n_animals + max_num + 1);
    for (int i = 1; i <= n_animals + max_num; ++i) {
        extended_species[i] = species[(i - 1) % n_animals + 1];
    }
    
    int total_len = n_animals + max_num;
    vector<vector<int>> win_state(total_len + 1, vector<int>(max_num + 1, 0));
    vector<vector<int>> suffix_wins(total_len + 1, vector<int>(max_num + 2, 0));
    
    for (int i = total_len - 1; i >= 1; --i) {
        for (int j = max_num - 1; j >= 1; --j) {
            suffix_wins[i][j] = suffix_wins[i][j + 1];
            if (j + step_limit < max_num) {
                suffix_wins[i][j] -= win_state[i][j + step_limit];
            }
            
            bool next_player_same = (extended_species[i] == extended_species[i + 1]);
            bool can_win = false;
            
            if (next_player_same) {
                if (suffix_wins[i + 1][j + 1] > 0) can_win = true;
            } else {
                if (suffix_wins[i + 1][j + 1] == 0) can_win = true;
            }
            
            if (can_win) {
                win_state[i][j] = 1;
                suffix_wins[i][j]++;
            }
        }
    }
    
    for (int i = 1; i <= n_animals; ++i) {
        bool first_player_wins = false;
        for (int j = 1; j <= step_limit; ++j) {
            if (win_state[i][j]) {
                first_player_wins = true;
                break;
            }
        }
        cout << (first_player_wins ? extended_species[i] : (extended_species[i] ^ 1)) << " ";
    }
    cout << endl;
    return 0;
}

Problème 2 : Factorisation et Propriétés Arithmétiques

Étant donné un entier positif N, il s'agit de trouver tous les entiers T (0 < T < N) satisfaisant une condition arithmétique spécifique où le rapport de certaines expressions linéaires doit être un entier. En reformulant l'équation, on démontre que T peut s'exprimer sous la forme (2K-2)/(2K-1) * N. Pour que T soit un entier strictement positif et inférieur à N, le dénmoinateur 2K-1 doit être un diviseur impair strict de N.

L'algorithme consiste donc à énumérer tous les diviseurs de N jusqu'à √N, à filtrer les diviseurs impairs supérieurs à 1, et à calculer les valeurs correspondantes de T. Les résultats sont ensuite triés et dédupliqués pour garantir l'unicité.

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

using namespace std;

int main() {
    long long N;
    if (!(cin >> N)) return 0;
    
    vector<long long> valid_T;
    long long limit = sqrt(N);
    
    for (long long i = 1; i <= limit; ++i) {
        if (N % i == 0) {
            long long div1 = i;
            long long div2 = N / i;
            
            if (div1 % 2 != 0 && div1 > 1) {
                valid_T.push_back((N / div1) * (div1 - 1));
            }
            if (div2 % 2 != 0 && div2 > 1) {
                valid_T.push_back((N / div2) * (div2 - 1));
            }
        }
    }
    
    sort(valid_T.begin(), valid_T.end());
    valid_T.erase(unique(valid_T.begin(), valid_T.end()), valid_T.end());
    
    cout << valid_T.size() << " ";
    for (long long val : valid_T) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

Problème 3 : Plus Court Chemin avec Mécanique de Portails

Dans une grille de dimensions N x M, un agent doit se déplacer d'un point de départ à une destination. Outre les déplacements standards (coût de 1), l'agent peut créer des portails sur les murs adjacents. Seuls deux portails peuvent exister simultanément, et la téléportation entre deux portails coûte 1 unité de temps. La création d'un portail ne coûte rien, mais sa portée est limitée par la distance au mur.

Ce problème est modélisé comme un graphe pondéré. Les nœuds représentent les cellules valides de la grille. Les arêtes standard relient les cellules adjacentes avec un poids de 1. Des arêtes supplémentaires relient chaque cellule aux murs accessibles dans les quatre directions cardinales, avec un poids égal à la distance minimale vers un mur plus 1. L'algorithme de Dijkstra est ensuite appliqué pour trouver le chemin le plus court, garantissant une complexité optimale et évitant les pitfalls de l'algorithme SPFA sur ce type de graphe.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <climits>

using namespace std;

struct Edge {
    int to, weight;
};

int main() {
    int rows, cols;
    if (!(cin >> rows >> cols)) return 0;
    
    vector<string> grid(rows);
    int start_node = -1, end_node = -1;
    
    for (int i = 0; i < rows; ++i) {
        cin >> grid[i];
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'C') start_node = i * cols + j;
            if (grid[i][j] == 'F') end_node = i * cols + j;
        }
    }
    
    int total_nodes = rows * cols;
    vector<vector<Edge>> adj(total_nodes);
    
    auto add_edge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
    };
    
    for (int i = 1; i < rows - 1; ++i) {
        for (int j = 1; j < cols - 1; ++j) {
            if (grid[i][j] == '#') continue;
            int u = i * cols + j;
            
            if (grid[i+1][j] != '#') add_edge(u, (i+1)*cols + j, 1);
            if (grid[i-1][j] != '#') add_edge(u, (i-1)*cols + j, 1);
            if (grid[i][j+1] != '#') add_edge(u, i*cols + (j+1), 1);
            if (grid[i][j-1] != '#') add_edge(u, i*cols + (j-1), 1);
            
            int r_down = i, r_up = i, c_right = j, c_left = j;
            while (r_down + 1 < rows && grid[r_down+1][j] != '#') r_down++;
            while (r_up - 1 >= 0 && grid[r_up-1][j] != '#') r_up--;
            while (c_right + 1 < cols && grid[i][c_right+1] != '#') c_right++;
            while (c_left - 1 >= 0 && grid[i][c_left-1] != '#') c_left--;
            
            int min_dist = min({r_down - i, i - r_up, c_right - j, j - c_left}) + 1;
            
            add_edge(u, r_down * cols + j, min_dist);
            add_edge(u, r_up * cols + j, min_dist);
            add_edge(u, i * cols + c_right, min_dist);
            add_edge(u, i * cols + c_left, min_dist);
        }
    }
    
    vector<int> dist(total_nodes, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start_node] = 0;
    pq.push({0, start_node});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (const auto& edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    
    if (dist[end_node] == INT_MAX) cout << "nemoguce" << endl;
    else cout << dist[end_node] << endl;
    
    return 0;
}

Problème 4 : Connectivité Dynamique et Ensembles Disjoints

Le problème consiste à gérer la connectivité de N villes sur M jours. Chaque jour i, des routes sont construites entre les villes a et b si leur plus grand commun diviseur (PGCD) est égal à M - i + 1. Il faut répondre à Q requêtes demandant le jour le plus précoce où deux villes données deviennent connectées.

La structure de données utilisée est l'Union-Find avec fusion par taille. Le temps de connexion est attribué comme poids au nœud enfant lors de la fusion. Pour répondre efficacement aux requêtes, l'arbre résultant est traité avec la technique des sauts binaires (Binary Lifting). Cela permet de trouver le Plus Proche Ancêtre Commun (LCA) et de calculer le poids maximum sur le chemin entre deux nœuds en temps logarithmique O(log N), améliorant ainsi significativement les performances par rapport à une remontée d'arbre naïve.

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

using namespace std;

const int MAXN = 100005;
const int LOG = 17;

int parent_node[MAXN], sz[MAXN], depth[MAXN];
int up[MAXN][LOG];
int max_time[MAXN][LOG];
int time_weight[MAXN];

int find_set(int v) {
    if (v == parent_node[v]) return v;
    return parent_node[v] = find_set(parent_node[v]);
}

void union_sets(int a, int b, int t) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b);
        parent_node[b] = a;
        sz[a] += sz[b];
        time_weight[b] = t; 
    }
}

int query_max(int u, int v) {
    if (find_set(u) != find_set(v)) return -1; 
    
    int ans = 0;
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; ++i) {
        if ((diff >> i) & 1) {
            ans = max(ans, max_time[u][i]);
            u = up[u][i];
        }
    }
    if (u == v) return ans;
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            ans = max({ans, max_time[u][i], max_time[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    ans = max({ans, max_time[u][0], max_time[v][0]});
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, q;
    if (!(cin >> n >> m >> q)) return 0;
    
    for (int i = 1; i <= n; ++i) {
        parent_node[i] = i;
        sz[i] = 1;
    }
    
    for (int i = 1; i <= m; ++i) {
        int step = m - i + 1;
        for (int j = 2 * step; j <= n; j += step) {
            union_sets(j - step, j, i);
        }
    }
    
    time_weight[0] = 0;
    for (int i = 1; i <= n; ++i) {
        if (find_set(i) == i) {
            parent_node[i] = 0;
            sz[0] += sz[i];
        }
    }
    
    vector<vector<int>> children(n + 1);
    for (int i = 1; i <= n; ++i) {
        children[parent_node[i]].push_back(i);
    }
    
    vector<int> queue;
    queue.push_back(0);
    depth[0] = 0;
    up[0][0] = 0;
    max_time[0][0] = 0;
    
    for (int i = 0; i < queue.size(); ++i) {
        int v = queue[i];
        for (int j = 1; j < LOG; ++j) {
            up[v][j] = up[up[v][j-1]][j-1];
            max_time[v][j] = max(max_time[v][j-1], max_time[up[v][j-1]][j-1]);
        }
        for (int child : children[v]) {
            depth[child] = depth[v] + 1;
            up[child][0] = v;
            max_time[child][0] = time_weight[child];
            queue.push_back(child);
        }
    }
    
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << query_max(u, v) << "\n";
    }
    
    return 0;
}