T1 : Tri par Ordre Croissant (II) Limite de Mémoire : 256 MoLimite de Temps : 1000 ms Description du Problème : Étant donné une permutation de longueur n, à chaque opération, vous pouvez sélectionner un élément et le déplacer au début ou à la fin. Détermniez le nombre minimum d'opérations nécessaires pour transformer la permutation en une séquence triée par ordre croissant. Format d'Entrée :

• La première ligne contient un entier positif n.
• La deuxième ligne contient n entiers positifs p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>n</sub>, représentant la permutation. Format de Sortie : Une seule ligne contenant un entier positif, le nombre minimum d'opérations. Contraintes :
• 30% des données : 1 ≤ n ≤ 10
• 60% des données : 1 ≤ n ≤ 103
• 100% des données : 1 ≤ n ≤ 105 Exemple : Entrée :7``3 5 4 6 1 7 2Sortie :4Explication : Déplacer 4 au début : 4 3 5 6 1 7 2Déplacer 3 au début : 3 4 5 6 1 7 2Déplacer 2 au début : 2 3 4 5 6 1 7Déplacer 1 au début : 1 2 3 4 5 6 7

L'idée clé est de considérer quels éléments peuvent rester en place. Étant donné que les éléments ne peuvent être déplacés qu'au début ou à la fin, les éléments qui restent devront former une sous-séquence continue dans la permutation originale. Le problème se ramène alors à trouver la plus longue sous-séquence d'éléments consécutifs (dans l'ordre croissant) qui apparaissent dans la permutation donnée dans le bon ordre relatif. Les autres éléments devront être déplacés. Pour optimiser la recherche de la plus longue sous-séquence continue, nous pouvons utiliser une structure de données pour stocker la position de chaque nombre. Cela permet un accès en O(1) à la position d'un nombre. Ensuite, nous pouvons itérer à travers les nombres, en construisant des séquences continues et en gardant une trace de la plus longue trouvée.

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

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

    int n;
    std::cin >> n;

    std::vector<int> p(n);
    std::map<int, int> pos; // Map pour stocker la position de chaque nombre
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
        pos[p[i]] = i;
    }

    int max_len = 0;
    std::vector<int> dp(n + 1, 0); // dp[i] stocke la longueur de la plus longue suite se terminant par i

    for (int i = 0; i < n; ++i) {
        int current_num = p[i];
        if (current_num == 1) {
            dp[current_num] = 1;
        } else {
            // Vérifier si le nombre précédent (current_num - 1) existe et est avant l'élément actuel
            if (pos.count(current_num - 1) && pos[current_num - 1] < i) {
                 dp[current_num] = dp[current_num - 1] + 1;
            } else {
                dp[current_num] = 1;
            }
        }
        max_len = std::max(max_len, dp[current_num]);
    }

    // Si aucun élément n'est dans l'ordre relatif correct, max_len pourrait être 0.
    // Si n > 0 et max_len est 0, cela signifie que même 1 n'a pas été trouvé ou la logique est faussée.
    // Si le tableau est vide (n=0), le résultat est 0. Si n>0, la plus courte séquence possible est 1.
    if (n > 0 && max_len == 0) {
        max_len = 1; // Au moins un élément peut être gardé.
    } else if (n == 0) {
        max_len = 0;
    }


    std::cout << n - max_len << std::endl;

    return 0;
}

T2 : Danse Collective Limite de Mémoire : 256 MoLimite de Temps : 1000 ms Description du Problème : n acteurs forment un cercle pour une danse collective. Initialement, chaque acteur est à sa position correspondante (1 à n). Il y a deux types de transformations :

• Rotation ('r') : L'acteur en position 1 va en position 2, 2 en 3, ..., n en 1.
• Flip ('f') : L'acteur en position 1 échange avec n, 2 avec n-1, etc. Si n est impair, la position (n+1)/2 reste inchangée. Étant donné une séquence de transformations, déterminez le numéro de l'acteur à chaque position à la fin de la danse. Format d'Entrée :
• La première ligne contient un entier n.
• La seconde ligne contient une chaîne de caractères s composée de 'r' et 'f'. Format de Sortie : n lignes, la i-ème ligne contenant le numéro de l'acteur à la i-ème position à la fin. Contraintes :
• Soit |s| la longueur de la chaîne d'entrée.
• 30% des données : 1 ≤ n ≤ 3000, 1 ≤ |s| ≤ 3000
• 60% des données : 1 ≤ n ≤ 100 000, 1 ≤ |s| ≤ 100 000
• 100% des données : 1 ≤ n ≤ 500 000, 1 ≤ |s| ≤ 500 000 Exemple : Entrée :4``rfrSortie :4``3``2``1Explication : (1,2,3,4) --r--> (4,1,2,3) (4,1,2,3) --f--> (3,2,1,4) (3,2,1,4) --r--> (4,3,2,1)

Il est utile de visualiser les transformations comme opérant sur un cercle. La transformation 'f' est une réflexion, tandis que 'r' est une rotation. Deux 'f' s'annulent. Pour les rtoations 'r', si le nombre de 'f' est pair, 'r' corrrespond à une rotation dans le sens horaire. Si le nombre de 'f' est impair, 'r' correspond à une rotation dans le sens antihoraire. Les rotations dans des directions opposées peuvent s'annuler. De plus, n rotations identiques s'annulent également. Nous pouvons suivre l'effet net des transformations sur les positions. Conservons un décalage pour les rotations et un indicateur pour la parité des flips. Le décalage représente le déplacement net dû aux rotations, et la parité du nombre de flips détermine si la séquence est inversée.

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

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

    long long n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    long long rotation_shift = 0; // Décalage net dû aux rotations
    int flip_count = 0;        // Nombre de flips

    for (char move : s) {
        if (move == 'r') {
            if (flip_count % 2 == 0) { // Si pas inversé, rotation horaire (déplacement vers la gauche des indices)
                rotation_shift = (rotation_shift - 1 + n) % n;
            } else { // Si inversé, rotation antihoraire (déplacement vers la droite des indices)
                rotation_shift = (rotation_shift + 1) % n;
            }
        } else { // move == 'f'
            flip_count++;
        }
    }

    bool is_reversed = (flip_count % 2 != 0);

    for (long long i = 0; i < n; ++i) {
        long long original_pos;
        if (!is_reversed) {
            // Cas non inversé : l'acteur à la position i est venu de (i + rotation_shift) % n
            original_pos = (i + rotation_shift) % n;
        } else {
            // Cas inversé : l'acteur à la position i est venu de (n - 1 - i + rotation_shift) % n
            original_pos = (n - 1 - i + rotation_shift + n) % n;
        }
        // Les positions sont 1-indexées dans la sortie
        std::cout << original_pos + 1 << "\n";
    }

    return 0;
}

T3 : Plus Petit Multiple Limite de Mémoire : 256 MoLimite de Temps : 1000 ms Description du Problème : Étant donné un nombre x, trouvez le plus petit nombre décimal composé uniquement de 0 et 1 qui est un multiple de x. Format d'Entrée :

• La première ligne contient un entier positif q, le nombre de requêtes.
• Les q lignes suivantes contiennent chacune un entier positif x<sub>i</sub>. Format de Sortie : q lignes, la i-ème ligne contenant la réponse pour la i-ème requête. Contraintes :
• 30% des données : 1 ≤ x ≤ 20
• 60% des données : 1 ≤ x ≤ 103
• 100% des données : 1 ≤ x ≤ 104, 1 ≤ q ≤ 103 Exemple : Entrée :3``5``27``527Sortie :10``1101111111``1101110111

Ce problème peut être résolu à l'aide d'une recherche en largeur (BFS) combinée au concept de reste modulo x. Puisque les nombres peuvent devenir très grands (dépassant la capacité de long long), nous travaillons avec les restes modulo x. Nous commençons avec le nombre 1 (qui a un reste de 1 modulo x). À chaque étape, nous pouvons soit ajouter un 0, soit ajouter un 1 à la fin du nombre actuel. Cela revient à calculer (reste_actuel * 10) % x ou (reste_actuel * 10 + 1) % x. Nous utilisons une file BFS pour explorer ces possibilités dans l'ordre, garantissant que le premier multiple de x trouvé (c'est-à-dire un nombre avec un reste de 0) est le plus petit. Pour reconstruire le nombre résultant, chaque nœud dans la file BFS doit stocker non seulement le reste, mais aussi le chemin (les chiffres 0 ou 1 ajoutés) ou un pointeur vers le nœud parent pour permettre la reconstruction rétroactive.

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

struct Node {
    int remainder;
    std::string path;
};

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

    int q;
    std::cin >> q;
    while (q--) {
        int x;
        std::cin >> x;

        std::queue<Node> q_bfs;
        // visited[r] stocke le chemin le plus court pour atteindre le reste r
        std::map<int, std::string> visited_paths;

        // Commencer avec le nombre 1
        q_bfs.push({1 % x, "1"});
        visited_paths[1 % x] = "1";

        std::string result = "";

        while (!q_bfs.empty()) {
            Node current = q_bfs.front();
            q_bfs.pop();

            if (current.remainder == 0) {
                result = current.path;
                break;
            }

            // Tenter d'ajouter '0'
            int next_rem_0 = (current.remainder * 10) % x;
            if (visited_paths.find(next_rem_0) == visited_paths.end()) {
                std::string next_path_0 = current.path + "0";
                visited_paths[next_rem_0] = next_path_0;
                q_bfs.push({next_rem_0, next_path_0});
            }

            // Tenter d'ajouter '1'
            int next_rem_1 = (current.remainder * 10 + 1) % x;
            if (visited_paths.find(next_rem_1) == visited_paths.end()) {
                 std::string next_path_1 = current.path + "1";
                 visited_paths[next_rem_1] = next_path_1;
                 q_bfs.push({next_rem_1, next_path_1});
            }
        }
        std::cout << result << "\n";
    }
    return 0;
}

T4 : Problème de Chemin (III) Limite de Mémoire : 256 MoLimite de Temps : 1000 ms Description du Problème : Il y a n villes dans un pays, numérotées de 1 à n. Les villes sont connectées par n-1 routes bidirectionnelles, formant un arbre. Il y a m touristes. Le i-ème touriste parcourt un chemin de la ville s<sub>i</sub> à la ville t<sub>i</sub>. Chaque ville visitée par un touriste (y compris les villes de départ et d'arrivée) est marquée. Calculez le nombre de fois où chaque ville est marquée. Format d'Entrée :

• La première ligne contient deux entiers positifs n, m.
• Les n-1 lignes suivantes décrivent les routes : u<sub>i</sub>, v<sub>i</sub>.
• Les m lignes suivantes décrivent les itinéraires des touristes : s<sub>i</sub>, t<sub>i</sub>. Format de Sortie : Une seule ligne contenant n entiers, où le i-ème entier est le nombre de fois où la ville i a été marquée. Contraintes :
• 30% des données : 1 ≤ n, m ≤ 100
• 60% des données : 1 ≤ n, m ≤ 103
• 100% des données : 1 ≤ n, m ≤ 105, 1 ≤ u<sub>i</sub>, v<sub>i</sub>, s<sub>i</sub>, t<sub>i</sub> ≤ nExemple : Entrée :4 3``1 2``2 3``4 2``1 4``3 4``2 4Sortie :1 3 1 3

L'approche naïve consistant à effectuer une recherche DFS/BFS pour chaque trajet et à marquer les villes ne sera pas efficace pour les grandes entrées (obtenant seulement 30% des points). Une solution plus efficace utilise les propriétés des arbres et des chemins. Pour chaque trajet (s<sub>i</sub>, t<sub>i</sub>), nous pouvons considérer l'effet de ce chemin sur les comptes de marquage des villes. L'idée est d'utiliser une technique de "différence" ou de mise à jour par parcours de racine. Pour un trajet de s à t, nous pouvons incrémenter un compteur à la ville s et à la ville t. Ensuite, nous pouvons décrémenter le compteur à leur plus proche ancêtre commun (LCA - Lowest Common Ancestor). Après avoir traité tous les trajets, nous pouvons effectuer un parcours DFS à partir de la racine pour propager ces changements. Le nombre final dans un nœud sera la somme des contributions de tous les chemins qui le traversent. Cela nécessite de précalculer les profondeurs, les parents et de pouvoir trouver rapidement le LCA.

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

const int MAXN = 100010;
const int LOGN = 18; // ceil(log2(MAXN))

std::vector<int> adj[MAXN];
int parent[MAXN][LOGN];
int depth[MAXN];
long long mark_counts[MAXN]; // Compteurs pour la technique de différence
int n, m;

void dfs_precompute(int u, int p, int d) {
    depth[u] = d;
    parent[u][0] = p;
    for (int v : adj[u]) {
        if (v != p) {
            dfs_precompute(v, u, d + 1);
        }
    }
}

void build_lca() {
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (parent[i][j - 1] != 0) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            } else {
                parent[i][j] = 0;
            }
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);

    for (int j = LOGN - 1; j >= 0; --j) {
        if (parent[u][j] != 0 && depth[parent[u][j]] >= depth[v]) {
            u = parent[u][j];
        }
    }

    if (u == v) return u;

    for (int j = LOGN - 1; j >= 0; --j) {
        if (parent[u][j] != 0 && parent[v][j] != 0 && parent[u][j] != parent[v][j]) {
            u = parent[u][j];
            v = parent[v][j];
        }
    }
    return parent[u][0];
}

// DFS pour propager les comptes de marquage
void dfs_propagate(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs_propagate(v, u);
            mark_counts[u] += mark_counts[v];
        }
    }
}

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

    std::cin >> n >> m;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Précalcul pour le LCA (en supposant la racine à 1)
    dfs_precompute(1, 0, 0);
    build_lca();

    for (int i = 0; i < m; ++i) {
        int s, t;
        std::cin >> s >> t;
        int ancestor = lca(s, t);

        // Incrémenter à s et t
        mark_counts[s]++;
        mark_counts[t]++;

        // Décrémenter au LCA (pour éviter de compter le chemin avant le LCA deux fois)
        // Si le LCA n'est pas s ou t, décrémenter son enfant qui est sur le chemin de s ou t
        if (ancestor != 0) { // S'assurer que le LCA existe
           mark_counts[ancestor] -= 2; // Correction : décrémenter 2 car on a incrémenté s et t séparément
        }
    }

    // Propager les comptes à travers l'arbre
    dfs_propagate(1, 0);

    // Afficher les résultats
    for (int i = 1; i <= n; ++i) {
        std::cout << mark_counts[i] << (i == n ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}