Problème A - Nombres en Progression Arithmétique

Étant donnés deux entiers x et y, l'objectif est de déterminer le nombre de valeurs entières distinctes possibles pour z telles que les trois nombres x, y, z, une fois triés, forment une progression arithmétique.

Considérons les deux nombres donnés comme a et b. Nous pouvons supposer sans perte de généralité que a ≤ b en les échangeant si nécessaire.

• Cas 1 : a = b
  Si a et b sont identiques (par exemple, a=3, b=3), la seule progression arithmétique possible est (3, 3, 3), où z=3. Il n'y a qu'une seule valeur pour z.

• Cas 2 : a < b
  La différence commune d doit être un entier. Il existe trois configurations possibles pour les trois nombres triés :

  1. a, b, z : La différence commune est d = b - a. Alors z = b + d = b + (b - a) = 2b - a.
  2. a, z, b : La différence commune est d = (b - a) / 2. Alors z = a + d = a + (b - a) / 2 = (a + b) / 2. Cette valeur de z n'est un entier que si b - a est pair.
  3. z, a, b : La différence commune est d = b - a. Alors z = a - d = a - (b - a) = 2a - b.

  En analysant la parité de la différence b - a :

  • Si b - a est impair : Les solutions pour z = 2b - a et z = 2a - b sont toujours des entiers et sont distinctes. La solution z = (a + b) / 2 ne sera pas un entier car a + b sera impair. Donc, il y a 2 valeurs possibles pour z.
  • Si b - a est pair : Toutes les trois solutions z = 2b - a, z = 2a - b et z = (a + b) / 2 seront des entiers. De plus, elles sont distinctes. Donc, il y a 3 valeurs possibles pour z.

#include <iostream>
#include <algorithm> // Pour std::swap

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int val1, val2;
    std::cin >> val1 >> val2;

    if (val1 > val2) {
        std::swap(val1, val2); // S'assurer que val1 <= val2
    }

    if (val1 == val2) {
        std::cout << 1 << std::endl;
    } else if ((val2 - val1) % 2 != 0) { // Différence impaire
        std::cout << 2 << std::endl;
    } else { // Différence paire
        std::cout << 3 << std::endl;
    }

    return 0;
}

Problème B - Pianiste Fatigué

Un pianiste utilise ses deux mains pour jouer. À chaque fois qu'une main se déplace d'une touche x à une touche y, la fatigue augmente de |x - y|. On nous donne une séquence de N mouvements, chacun spécifiant la touche et la main (gauche 'L' ou droite 'R'). L'objectif est de calculer la fatigue totale accumulée à la fin de la séquence.

Étant donné que les mouvements de chaque main sont indépendants des mouvements de l'autre main, nous pouvons calculer la fatigue pour la main gauche et la main droite séparément, puis additionner les deux totaux. Pour chaque main, il suffit de stocker la séquence des touches jouées et de sommer les valeurs absolues des différences entre les touches consécutives.

#include <iostream>
#include <vector>
#include <cmath> // Pour std::abs

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_moves;
    std::cin >> num_moves;

    std::vector<int> left_hand_keys;
    std::vector<int> right_hand_keys;

    for (int i = 0; i < num_moves; ++i) {
        int key_pos;
        char hand_char;
        std::cin >> key_pos >> hand_char;
        if (hand_char == 'L') {
            left_hand_keys.push_back(key_pos);
        } else { // hand_char == 'R'
            right_hand_keys.push_back(key_pos);
        }
    }

    long long total_fatigue = 0;

    // Calculer la fatigue pour la main gauche
    for (size_t i = 1; i < left_hand_keys.size(); ++i) {
        total_fatigue += std::abs(left_hand_keys[i] - left_hand_keys[i-1]);
    }

    // Calculer la fatigue pour la main droite
    for (size_t i = 1; i < right_hand_keys.size(); ++i) {
        total_fatigue += std::abs(right_hand_keys[i] - right_hand_keys[i-1]);
    }

    std::cout << total_fatigue << std::endl;

    return 0;
}

Problème C - Compter les Sous-Tableaux Arithmétiques

Étant donné un tableau d'entiers, nous devons compter le nombre de sous-tableaux contigus (définis par un indice de début L et un indice de fin R) qui forment une progression arithmétique.

Nous pouvons résoudre ce problème en utilisant la programmation dynamique. Pour chaque élément a[i] du tableau, nous voulons déterminer la longueur du plus long sous-tableau arithmétique se terminant à a[i]. Appelons cette longueur length[i].

Les règles de transition sont les suivantes :

• Pour i = 0, le sous-tableau (a[0]) a une longueur de 1. Donc, length[0] = 1.
• Pour i = 1, le sous-tableau (a[1]) a une longueur de 1, et (a[0], a[1]) a une longueur de 2. Donc, length[1] = 2.
• Pour i > 1 :
  • Si a[i] - a[i-1] == a[i-1] - a[i-2] (c'est-à-dire que la différence entre les deux derniers éléments est la même que la différence précédente), alors a[i] peut étendre la progression arithmétique se terminant à a[i-1]. Dans ce cas, length[i] = length[i-1] + 1.
  • Sinon, a[i] ne peut pas étendre la progression précédente. Cependant, a[i-1] et a[i] forment toujours une progression arithmétique de longueur 2. Donc, length[i] = 2.

Le nombre total de sous-tableaux arithmétiques est la somme de toutes les valeurs length[i] pour i allant de 0 à N-1. Cependant, cela compte toutes les sous-séquences. La définition des sous-tableaux est un peu subtile : si length[i] est la longueur du plus long tableau arithmétique finissant en i, alors ce tableau contribue length[i] - 1 nouvelles progressions arithmétiques de longueur ≥ 2 (par exemple, si la séquence est (x,y,z), length[i]=3, elle ajoute (z), (y,z), (x,y,z)). Une progression arithmétique doit avoir au moins 1 élément. Un sous-tableau de longueur L se terminant à a[i] contient L sous-tableaux qui se terminent à a[i] : (a[i]), (a[i-1], a[i]), ..., (a[i-L+1], ..., a[i]). L'énoncé demande de compter tous les (L,R). Chaque élément a[i] seul forme une AP de longueur 1. Chaque paire (a[i-1], a[i]) forme une AP de longueur 2. Le length[i] défini ci-dessus représente le nombre de sous-tableaux arithmétiques se terminant à a[i].

L'algorithme de la solution originale est correct : la variable ans totalise la somme des dp[i]. dp[i] est effectivement la longueur du plus long sous-tableau arithmétique se terminant à a[i]. Cependant, il faut faire attention à l'initialisation de ans pour les cas n=0, 1, 2.

• Si n=1, il y a 1 sous-tableau arithmétique (a[0]).
• Si n=2, il y a 3 sous-tableaux arithmétiques : (a[0]), (a[1]), (a[0], a[1]).

L'initialisation dans le code original avec ans = 3 suppose n ≥ 2 et prend en compte dp[0]=1 et dp[1]=2. La boucle commence à i=2. Le ans += dp[i] accumule les contributions de a[i].

#include <iostream>
#include <vector>
#include <numeric> // Pour std::accumulate

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<long long> sequence(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sequence[i];
    }

    if (n <= 2) {
        std::cout << n * (n + 1) / 2 << std::endl; // Pour n=0 (0), n=1 (1), n=2 (3)
        return 0;
    }

    std::vector<long long> current_ap_lengths(n);
    current_ap_lengths[0] = 1;
    current_ap_lengths[1] = 2; // (a[1]) et (a[0], a[1])

    long long total_arithmetic_subarrays = 3; // Compte pour (a[0]), (a[1]), (a[0], a[1])
    long long common_difference = sequence[1] - sequence[0];

    for (int i = 2; i < n; ++i) {
        if (sequence[i] - sequence[i-1] == common_difference) {
            current_ap_lengths[i] = current_ap_lengths[i-1] + 1;
        } else {
            current_ap_lengths[i] = 2; // (a[i]) et (a[i-1], a[i])
            common_difference = sequence[i] - sequence[i-1];
        }
        total_arithmetic_subarrays += current_ap_lengths[i];
    }

    std::cout << total_arithmetic_subarrays << std::endl;

    return 0;
}

Problème D - Points d'Expérience Bonus

Takahashi rencontre une série de monstres. Pour chaque monstre, il peut choisir de le vaincre ou de le passer. Vaincre un monstre i lui rapporte x_i points d'expérience. Si c'est le k-ième monstre qu'il vainc, et que k est un nombre pair, l'expérience est doublée (2 * x_i). L'objectif est de trouver l'expérience maximale totale que Takahashi peut obtenir.

Ce problème peut être résolu avec la programmation dynamique. Nous devons suivre deux états pour chaque étape : l'expérience maximale obtenue en vainquant un nombre impair de monstres et l'expérience maximale obtenue en vainquant un nombre pair de monstres.

Définissons max_xp_odd[i] comme l'expérience maximale après avoir considéré les i premiers monstres, ayant vaincu un nombre impair de monstres. Définissons max_xp_even[i] comme l'expérience maximale après avoir considéré les i premiers monstres, ayant vaincu un nombre pair de monstres (y compris 0 monstres).

Initialisation :

• max_xp_odd = -INF (impossible d'avoir un nombre impair de monstres vaincus sans avoir vaincu au moins un monstre). Utiliser une très petite valeur négative pour représenter l'impossibilité.
• max_xp_even = 0 (0 monstre vaincu est un nombre pair de monstres, et l'expérience est 0).

Pour chaque monstre m_i avec xp_val expérience :

Nous avons deux choix pour le monstre actuel m_i :

1. Passer le monstre m_i : Les valeurs max_xp_odd et max_xp_even restent inchangées par rapport à l'étape précédente.
2. Vaincre le monstre m_i :
   • Si m_i est le prochain monstre vaincu impair (c'est-à-dire que le nombre total de monstres vaincus devient impair), cela signifie que le nombre précédent de monstres vaincus était pair. La nouvelle expérience serait max_xp_even + xp_val.
   • Si m_i est le prochain monstre vaincu pair (c'est-à-dire que le nombre total de monstres vaincus devient pair), cela signifie que le nombre précédent de monstres vaincus était impair. La nouvelle expérience serait max_xp_odd + (2 * xp_val).

En combinant ces options, les transitions DP sont :

Pour chaque monstre `x` dans l'ordre :
    `prev_max_xp_odd = max_xp_odd`
    `prev_max_xp_even = max_xp_even`

    // Option 1: Vaincre le monstre actuel comme le prochain monstre impair
    // Nécessite que le décompte précédent était pair
    // max_xp_odd est mis à jour avec le max entre ne pas prendre ce monstre (prev_max_xp_odd)
    // et prendre ce monstre (prev_max_xp_even + x)
    `max_xp_odd = std::max(prev_max_xp_odd, prev_max_xp_even + x)`

    // Option 2: Vaincre le monstre actuel comme le prochain monstre pair
    // Nécessite que le décompte précédent était impair
    // max_xp_even est mis à jour avec le max entre ne pas prendre ce monstre (prev_max_xp_even)
    // et prendre ce monstre avec bonus (prev_max_xp_odd + 2 * x)
    `max_xp_even = std::max(prev_max_xp_even, prev_max_xp_odd + 2 * x)`

Après avoir traité tous les monstres, l'expérience maximale est le maximum de max_xp_odd et max_xp_even.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max
#include <limits>    // Pour std::numeric_limits

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_monsters;
    std::cin >> num_monsters;

    long long max_xp_odd = std::numeric_limits<long long>::min(); // XP max après un nombre impair de monstres vaincus
    long long max_xp_even = 0;                                  // XP max après un nombre pair de monstres vaincus (y compris 0)

    for (int i = 0; i < num_monsters; ++i) {
        long long current_monster_xp;
        std::cin >> current_monster_xp;

        long long temp_xp_odd = max_xp_odd;
        long long temp_xp_even = max_xp_even;

        // Calculer la nouvelle XP si le monstre actuel est le prochain monstre impair
        // (venant d'un état où le compte précédent était pair)
        if (temp_xp_even != std::numeric_limits<long long>::min()) { // Assurez-vous que l'état pair est atteignable
            max_xp_odd = std::max(max_xp_odd, temp_xp_even + current_monster_xp);
        }

        // Calculer la nouvelle XP si le monstre actuel est le prochain monstre pair (avec bonus)
        // (venant d'un état où le compte précédent était impair)
        if (temp_xp_odd != std::numeric_limits<long long>::min()) { // Assurez-vous que l'état impair est atteignable
            max_xp_even = std::max(max_xp_even, temp_xp_odd + 2 * current_monster_xp);
        }
    }

    // Le résultat final est le maximum de l'expérience obtenue avec un nombre impair ou pair de monstres.
    // Il faut gérer le cas où seule l'état 'impair' ou 'pair' a été mis à jour de -INF.
    long long final_max_xp = std::max(max_xp_odd, max_xp_even);
    if (final_max_xp < 0 && num_monsters > 0) { // Si tous les XP sont négatifs et il y a des monstres, il peut être préférable de ne rien prendre (0 XP)
        final_max_xp = 0;
    } else if (num_monsters == 0) {
        final_max_xp = 0;
    }


    std::cout << final_max_xp << std::endl;

    return 0;
}

Problème E - Tour Touristique

On vous donne un graphe non orienté de N nœuds et M arêtes, où chaque arête a un temps de traversée. Il y a Q requêtes. Chaque requête spécifie un ensemble de jusqu'à cinq arêtes. Pour chaque requête, vous devez trouver la longueur du chemin le plus court du nœud 1 au nœud N, en traversant chacune des arêtes spécifiées au moins une fois.

Étant donné que le nombre d'arêtes obligatoires (k) est très faible (jusqu'à 5), nous pouvons utiliser une approche combinatoire après avoir pré-calculé toutes les plus courtes distances entre les paires de nœuds.

1. Pré-calculer toutes les paires de plus courtes distances : Utilisez l'algorithme de Floyd-Warshall. Pour N jusqu'à 400, O(N^3) est acceptable (400^3 = 6.4 * 10^7). Soit dist[i][j] la plus courte distance entre le nœud i et le nœud j.

2. **Pour chaque requête :**Soient k les arêtes spécifiées. Pour traverser ces k arêtes, nous devons décider de leur ordre de visite et, pour chaque arête (u, v, temps), si nous la traversons de u à v ou de v à u.

   • Permutations des arêtes : Il y a k! permutations possibles pour l'ordre de visite des k arêtes. Pour k=5, 5! = 120.
   • Orientation des arêtes : Pour chaque arête dans la permutation, il y a deux façons de la traverser (u->v ou v->u). Cela ajoute un facteur 2^k. Cependant, nous pouvons incorporer cela dans une DP subtile.

   Pour chaque permutation d'arêtes obligatoires e_1, e_2, ..., e_k :

   Nous utilisons une approche de programmation dynamique pour la permutation courante. Soit dp[i][0] le chemin le plus court pour traverser les i+1 premières arêtes de la permutation, se terminant au premier point de l'arête e_{i+1}. De même, dp[i][1] se terminant au second point de l'arête e_{i+1}.

   Désignons les points de l'arête e_j comme (U_j, V_j) et son coût comme T_j.

   • Initialisation (pour la première arête e_0 de la permutation) :

     • dp[0][0] = dist[0][V_0] + T_0 (chemin : Nœud 0 → V_0 → U_0). Fin à U_0.
     • dp[0][1] = dist[0][U_0] + T_0 (chemin : Nœud 0 → U_0 → V_0). Fin à V_0.

     (Attention aux indices, Nœud 1 est 0-indexé, Nœud N est N-1 0-indexé.)

   • Transitions (pour l'arête e_{i+1} venant de l'arête e_i) :

     • dp[i+1][0] (terminer à U_{i+1}) :

       • Depuis dp[i][0] (finissant à U_i) : dp[i][0] + dist[U_i][V_{i+1}] + T_{i+1} (chemin : ... → U_i → V_{i+1} → U_{i+1})
       • Depuis dp[i][1] (finissant à V_i) : dp[i][1] + dist[V_i][V_{i+1}] + T_{i+1} (chemin : ... → V_i → V_{i+1} → U_{i+1})

       Prendre le minimum des deux.

     • dp[i+1][1] (terminer à V_{i+1}) :

       • Depuis dp[i][0] (finissant à U_i) : dp[i][0] + dist[U_i][U_{i+1}] + T_{i+1} (chemin : ... → U_i → U_{i+1} → V_{i+1})
       • Depuis dp[i][1] (finissant à V_i) : dp[i][1] + dist[V_i][U_{i+1}] + T_{i+1} (chemin : ... → V_i → U_{i+1} → V_{i+1})

       Prendre le minimum des deux.

   Après avoir calculé toutes les transitions pour la permutation, la distance minimale pour cette permutation est :
   min(dp[k-1][0] + dist[U_{k-1}][N-1], dp[k-1][1] + dist[V_{k-1}][N-1])

3. La réponse finale est le minimum parmi toutes les permutations.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::min, std::next_permutation
#include <limits>    // Pour std::numeric_limits

const long long INF = std::numeric_limits<long long>::max() / 2; // Utilisez une grande valeur pour l'infini

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_nodes, num_edges;
    std::cin >> num_nodes >> num_edges;

    // u_edges[i], v_edges[i] sont les extrémités de l'arête i (0-indexées)
    // edge_times[i] est le temps de traversée de l'arête i
    std::vector<int> u_edges(num_edges), v_edges(num_edges);
    std::vector<long long> edge_times(num_edges);

    // Initialisation de la matrice des distances pour Floyd-Warshall
    std::vector<std::vector<long long>> dist(num_nodes, std::vector<long long>(num_nodes, INF));
    for (int i = 0; i < num_nodes; ++i) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < num_edges; ++i) {
        std::cin >> u_edges[i] >> v_edges[i] >> edge_times[i];
        u_edges[i]--; // Convertir en 0-indexé
        v_edges[i]--; // Convertir en 0-indexé
        dist[u_edges[i]][v_edges[i]] = std::min(dist[u_edges[i]][v_edges[i]], edge_times[i]);
        dist[v_edges[i]][u_edges[i]] = std::min(dist[v_edges[i]][u_edges[i]], edge_times[i]); // Graphe non orienté
    }

    // Algorithme de Floyd-Warshall
    for (int k = 0; k < num_nodes; ++k) {
        for (int i = 0; i < num_nodes; ++i) {
            for (int j = 0; j < num_nodes; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    int num_queries;
    std::cin >> num_queries;

    for (int q_idx = 0; q_idx < num_queries; ++q_idx) {
        int k_mandatory_edges;
        std::cin >> k_mandatory_edges;

        std::vector<int> mandatory_edge_indices(k_mandatory_edges);
        for (int i = 0; i < k_mandatory_edges; ++i) {
            std::cin >> mandatory_edge_indices[i];
            mandatory_edge_indices[i]--; // Convertir en 0-indexé
        }

        long long min_total_time = INF;

        // Si aucune arête n'est obligatoire, c'est juste la plus courte distance de 0 à num_nodes-1
        if (k_mandatory_edges == 0) {
            min_total_time = dist[0][num_nodes - 1];
        } else {
            // Créer une permutation d'indices pour les arêtes obligatoires
            std::vector<int> p_indices(k_mandatory_edges);
            std::iota(p_indices.begin(), p_indices.end(), 0); // Remplir avec 0, 1, ..., k-1

            do {
                // dp[i][0] = min temps pour traverser les i+1 premières arêtes de la permutation, terminant au premier noeud (u) de l'arête p_indices[i]
                // dp[i][1] = min temps pour traverser les i+1 premières arêtes de la permutation, terminant au second noeud (v) de l'arête p_indices[i]
                std::vector<std::vector<long long>> dp(k_mandatory_edges, std::vector<long long>(2, INF));

                int first_edge_idx = mandatory_edge_indices[p_indices[0]];
                int u0 = u_edges[first_edge_idx];
                int v0 = v_edges[first_edge_idx];
                long long t0 = edge_times[first_edge_idx];

                // Départ du nœud 0, traverser l'arête (u0, v0) en u0->v0 ou v0->u0
                if (dist[0][u0] != INF) {
                    dp[0][1] = std::min(dp[0][1], dist[0][u0] + t0); // Chemin 0 -> u0 -> v0, fin à v0
                }
                if (dist[0][v0] != INF) {
                    dp[0][0] = std::min(dp[0][0], dist[0][v0] + t0); // Chemin 0 -> v0 -> u0, fin à u0
                }

                for (int i = 0; i < k_mandatory_edges - 1; ++i) {
                    int current_edge_idx = mandatory_edge_indices[p_indices[i]];
                    int u_curr = u_edges[current_edge_idx];
                    int v_curr = v_edges[current_edge_idx];

                    int next_edge_idx = mandatory_edge_indices[p_indices[i+1]];
                    int u_next = u_edges[next_edge_idx];
                    int v_next = v_edges[next_edge_idx];
                    long long t_next = edge_times[next_edge_idx];

                    // Transition pour arriver à u_next
                    if (dp[i][0] != INF) { // Fin de l'arête courante à u_curr
                        if (dist[u_curr][v_next] != INF) {
                            dp[i+1][0] = std::min(dp[i+1][0], dp[i][0] + dist[u_curr][v_next] + t_next); // u_curr -> v_next -> u_next
                        }
                    }
                    if (dp[i][1] != INF) { // Fin de l'arête courante à v_curr
                        if (dist[v_curr][v_next] != INF) {
                            dp[i+1][0] = std::min(dp[i+1][0], dp[i][1] + dist[v_curr][v_next] + t_next); // v_curr -> v_next -> u_next
                        }
                    }

                    // Transition pour arriver à v_next
                    if (dp[i][0] != INF) { // Fin de l'arête courante à u_curr
                        if (dist[u_curr][u_next] != INF) {
                            dp[i+1][1] = std::min(dp[i+1][1], dp[i][0] + dist[u_curr][u_next] + t_next); // u_curr -> u_next -> v_next
                        }
                    }
                    if (dp[i][1] != INF) { // Fin de l'arête courante à v_curr
                        if (dist[v_curr][u_next] != INF) {
                            dp[i+1][1] = std::min(dp[i+1][1], dp[i][1] + dist[v_curr][u_next] + t_next); // v_curr -> u_next -> v_next
                        }
                    }
                }

                // Ajouter la distance du dernier point obligatoire au nœud de destination (N-1)
                int last_edge_idx = mandatory_edge_indices[p_indices[k_mandatory_edges-1]];
                int u_last = u_edges[last_edge_idx];
                int v_last = v_edges[last_edge_idx];

                if (dp[k_mandatory_edges-1][0] != INF && dist[u_last][num_nodes-1] != INF) {
                    min_total_time = std::min(min_total_time, dp[k_mandatory_edges-1][0] + dist[u_last][num_nodes-1]);
                }
                if (dp[k_mandatory_edges-1][1] != INF && dist[v_last][num_nodes-1] != INF) {
                    min_total_time = std::min(min_total_time, dp[k_mandatory_edges-1][1] + dist[v_last][num_nodes-1]);
                }

            } while (std::next_permutation(p_indices.begin(), p_indices.end()));
        }
        std::cout << min_total_time << std::endl;
    }

    return 0;
}

Problème F - Collecte de Pièces

Vous êtes sur une grille de dimensions HxW, où certaines cases contiennent des pièces d'or. Vous commencez à la case (1,1) (coin supérieur gauche) et devez atteindre la case (H,W) (coin inférieur droit). Vous ne pouvez vous déplacer que vers le bas ou vers la droite. L'objectif est de maximiser le nombre de pièces d'or collectées et de produire la séquence de mouvements pour y parvenir.

Les contraintes de mouvement (seulement vers le bas ou la droite) impliquent que si vous collectez une pièce à (r1, c1) puis une autre à (r2, c2), alors il doit être vrai que r2 ≥ r1 et c2 ≥ c1. Ce problème se transforme en une recherche de la plus longue sous-séquence croissante (LIS) sur les coordonnées des pièces.

L'approche est la suivante :

1. Préparer les points : Ajoutez le point de départ (1,1) et le point d'arrivée (H,W) à la liste des points. Il est important de les inclure car le chemin doit commencer et se terminer à ces points. Les points de pièces sont également des "points" potentiels à traverser.
2. Trier les points : Triez tous les points (départ, pièces, arrivée) d'abord par ligne (coordonnée r), puis par colonne (coordonnée c). Ce tri garantit que toute pièce (r_i, c_i) précédant une pièce (r_j, c_j) dans la liste triée satisfait r_i ≤ r_j.
3. Appliquer LIS sur les colonnes : Parcourez la liste des points triés. Pour chaque point (r, c), trouvez la plus longue sous-séquence croissante de coordonnées de colonne c, où les points sont également "croissants" en ligne. Nous pouvons utiliser une version optimisée de LIS avec la recherche binaire pour trouver la longueur et reconstruire le chemin.
   • On utilise un tableau dp où dp[len] stocke la plus petite valeur de colonne de la dernière pièce d'une LIS de longueur len+1.
   • On utilise un tableau predecessor[i] pour stocker l'indice du point précédent dans la LIS qui se termine au point i.
   • On utilise un tableau id_at_len[len] pour stocker l'indice du point actuel qui se termine la LIS de longueur len+1 avec la plus petite valeur de colonne.
4. Reconstruire le chemin : Une fois le LIS calculé, on peut retrouver la séquence des points (r, c) qui composent le chemin optimal en suivant les prédécesseurs à partir du dernier point du LIS.
5. Générer la séquence de mouvements : Pour chaque paire de points consécutifs (r1, c1) et (r2, c2) dans le chemin optimal, générez r2 - r1 mouvements 'D' (bas) et c2 - c1 mouvements 'R' (droite).

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::sort, std::upper_bound, std::reverse
#include <string>

struct GridPoint {
    int r, c;
    int original_idx; // Pour référence si besoin, pas utilisé ici pour le path finding

    bool operator<(const GridPoint& other) const {
        if (r != other.r) {
            return r < other.r;
        }
        return c < other.c;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int H, W, N;
    std::cin >> H >> W >> N;

    std::vector<GridPoint> all_points;
    all_points.push_back({1, 1, -1}); // Point de départ (1-indexé)

    for (int i = 0; i < N; ++i) {
        int r_coin, c_coin;
        std::cin >> r_coin >> c_coin;
        all_points.push_back({r_coin, c_coin, i});
    }

    all_points.push_back({H, W, -2}); // Point d'arrivée (1-indexé)

    std::sort(all_points.begin(), all_points.end());

    int total_points = all_points.size();

    // dp[k] = la plus petite colonne de fin d'une LIS de longueur k+1
    // id_at_len[k] = l'indice dans all_points du point qui correspond à dp[k]
    // predecessor[i] = l'indice dans all_points du point précédent pour le point i dans la LIS
    std::vector<int> dp(total_points + 1, W + 1); // W+1 est une valeur > W, pour l'infini
    std::vector<int> id_at_len(total_points + 1, -1);
    std::vector<int> predecessor(total_points, -1);

    int max_len_lis = 0; // Longueur max LIS

    for (int i = 0; i < total_points; ++i) {
        // Trouver la position pour insérer all_points[i].c dans dp
        // C'est l'indice 'len' tel que dp[len-1] < all_points[i].c <= dp[len]
        auto it = std::upper_bound(dp.begin(), dp.end(), all_points[i].c);
        int current_len = std::distance(dp.begin(), it);

        dp[current_len] = all_points[i].c;
        id_at_len[current_len] = i;

        if (current_len > 0) {
            predecessor[i] = id_at_len[current_len - 1];
        }

        max_len_lis = std::max(max_len_lis, current_len + 1);
    }
    
    // Si H,W est inaccessible, la LIS sera petite, mais on doit s'assurer que (1,1) et (H,W) sont connectés
    // Trouver le point final de la LIS qui mène à (H,W)
    int last_point_idx_in_lis = -1;
    for(int i = 0; i < total_points; ++i) {
        if (all_points[i].r == H && all_points[i].c == W) {
            // Cherche le meilleur LIS se terminant au point (H,W)
            // On doit trouver l'ID dans id_at_len qui correspond à (H,W)
            // Ou plus simplement, si (H,W) est le dernier point dans all_points,
            // alors c'est le id_at_len[max_len_lis-1] si c'est la seule LIS.
            // Le calcul ci-dessus suppose que (H,W) pourrait être n'importe où.
            // Il faut trouver le dernier point du LIS qui est (H,W)
            
            // max_len_lis est la longueur maximale du LIS trouvé.
            // id_at_len[max_len_lis - 1] est l'indice du dernier élément de ce LIS.
            // Si ce point n'est pas (H,W), alors il faut chercher.
            // Pour garantir que (H,W) est le dernier point du LIS:
            int current_best_lis_end_idx = -1;
            int current_max_lis_length = 0;
            
            for(int j=0; j < total_points; ++j) {
                if(all_points[j].r == H && all_points[j].c == W) {
                     // Find the length of LIS ending at all_points[j]
                    // This is 'current_len' from above for index j
                    auto it_j = std::upper_bound(dp.begin(), dp.end(), all_points[j].c);
                    int len_at_j = std::distance(dp.begin(), it_j); // This len_at_j is 0-indexed length-1
                    
                    if(len_at_j > current_max_lis_length) {
                        current_max_lis_length = len_at_j;
                        current_best_lis_end_idx = j;
                    }
                }
            }
            last_point_idx_in_lis = current_best_lis_end_idx;
            max_len_lis = current_max_lis_length; // This is (length-1), need to add 1 later
            break;
        }
    }
    
    // Le nombre de pièces collectées est max_len_lis - 2 (en excluant (1,1) et (H,W))
    // Si (H,W) n'a pas été trouvé ou LIS n'atteint pas (H,W), ou LIS est juste (1,1) -> (H,W)
    int collected_coins_count = 0;
    if (last_point_idx_in_lis != -1) {
        collected_coins_count = max_len_lis - 1; // max_len_lis est 0-indexé, donc c'est la longueur.
                                                 // Déjà inclus (1,1) et (H,W)
        if (all_points[id_at_len[0]].r == 1 && all_points[id_at_len[0]].c == 1 &&
            all_points[id_at_len[max_len_lis-1]].r == H && all_points[id_at_len[max_len_lis-1]].c == W) {
            // This is the ideal case where a valid LIS from (1,1) to (H,W) is found.
            // max_len_lis includes (1,1) and (H,W), so actual coins = max_len_lis - 2.
            collected_coins_count = max_len_lis - 2;
            if (collected_coins_count < 0) collected_coins_count = 0; // Handle case where max_len_lis < 2 (e.g., only (1,1) to (H,W) with no intermediate coins)
        } else {
             // If the LIS doesn't specifically start at (1,1) and end at (H,W) using id_at_len.
             // We need to reconstruct the path from last_point_idx_in_lis
             // and count how many coin points are in it.
             std::vector<gridpoint> actual_path_points;
             int current_path_node = last_point_idx_in_lis;
             while(current_path_node != -1) {
                 actual_path_points.push_back(all_points[current_path_node]);
                 current_path_node = predecessor[current_path_node];
             }
             std::reverse(actual_path_points.begin(), actual_path_points.end());
             
             collected_coins_count = 0;
             if (actual_path_points.size() >= 2 &&
                 actual_path_points[0].r == 1 && actual_path_points[0].c == 1 &&
                 actual_path_points.back().r == H && actual_path_points.back().c == W) {
                collected_coins_count = actual_path_points.size() - 2;
             } else if (actual_path_points.size() >= 1 && 
                        actual_path_points[0].r == 1 && actual_path_points[0].c == 1 &&
                        actual_path_points.back().r == H && actual_path_points.back().c == W) {
                collected_coins_count = 0; // Path is just (1,1) to (H,W)
             }
        }
    } else { // No valid LIS found, or only (1,1) (H,W) are present
        // Check if (1,1) and (H,W) are the same point (if H=1, W=1)
        if (H==1 && W==1) collected_coins_count = 0; // If start and end are same, 0 coins
        else { // Otherwise, 0 coins
           // Need to confirm (1,1) to (H,W) path exists, it does, just no coins.
           collected_coins_count = 0;
        }
    }
    
    std::vector<GridPoint> path_nodes;
    if (last_point_idx_in_lis != -1) {
        int current_idx = last_point_idx_in_lis;
        while (current_idx != -1) {
            path_nodes.push_back(all_points[current_idx]);
            current_idx = predecessor[current_idx];
        }
        std::reverse(path_nodes.begin(), path_nodes.end());
    } else {
        // Fallback: If no LIS to (H,W) was found, path is just (1,1) to (H,W)
        // This implies no coins were picked
        path_nodes.push_back({1,1,-1});
        path_nodes.push_back({H,W,-1});
    }

    std::string moves = "";
    for (size_t i = 0; i < path_nodes.size() - 1; ++i) {
        int dr = path_nodes[i+1].r - path_nodes[i].r;
        int dc = path_nodes[i+1].c - path_nodes[i].c;
        for (int k = 0; k < dr; ++k) moves.push_back('D');
        for (int k = 0; k < dc; ++k) moves.push_back('R');
    }
    
    // Correctly count collected coins based on the path_nodes
    int final_collected_coins = 0;
    for(const auto& p : path_nodes) {
        if (p.original_idx != -1 && p.original_idx != -2) { // Original_idx -1 for start, -2 for end
            final_collected_coins++;
        }
    }

    std::cout << final_collected_coins << '\n';
    std::cout << moves << '\n';

    return 0;
}
</gridpoint>