1. Simulation de direction

Considérons un robot nommé Niu Niu qui se déplace sur un plan bidimensionnel. Il commence à la position (0,0) et fait face au nord (direction positive de l'axe y). Les commandes disponibles sont :

• W : avancer d'une case dans la direction actuelle
• A : tourner de 90 degrés vers la gauche
• D : tourner de 90 degrés vers la droite
• S : rester sur place Étant donné une séquence de commandes, calculez la position finale du robot.

Implémentation en C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    // Directions: nord, est, sud, ouest
    int vecteurs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    string instructions;
    cin >> instructions;
    
    int posX = 0, posY = 0;
    int indiceDirection = 0;
    
    for (char cmd : instructions) {
        switch (cmd) {
            case 'W':
                posX += vecteurs[indiceDirection][0];
                posY += vecteurs[indiceDirection][1];
                break;
            case 'A':
                indiceDirection = (indiceDirection + 3) % 4;
                break;
            case 'D':
                indiceDirection = (indiceDirection + 1) % 4;
                break;
            default:
                break;
        }
    }
    
    cout << posX << " " << posY << endl;
    return 0;
}

2. Comptage de paires

Étant donné un tableau de N entiers et un entier non négatif X, déterminez le nombre de paires d'indices (i, j) telles que a[i] + a[j] = X.

Solution utilisant une table de hachage

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int taille, valeurCible;
    cin >> taille >> valeurCible;
    
    long long compteur = 0;
    unordered_map<int, int> frequences;
    
    for (int i = 0; i < taille; ++i) {
        int valeur;
        cin >> valeur;
        
        int complement = valeurCible - valeur;
        if (frequences.find(complement) != frequences.end()) {
            compteur += frequences[complement];
        }
        
        // Gérer les paires avec le même élément
        if (complement == valeur) {
            compteur++;
        }
        
        frequences[valeur]++;
    }
    
    cout << compteur << endl;
    return 0;
}

3. Transformation de tableau

On dispose d'un tableau initial de longueur n rempli de zéros. À chaque opération, on peut choisir un intervalle [l, r] où chaque élément doit être incrémenté de 1 ou mulitplié par 2 (les éléments de l'intervalle sont traités indépendamment). Étant donné un tableau cible b, quel est le nombre minimum d'opérations nécessaires pour transformer le tableau initial en b ? Règle découverte : Pour transformer 0 en un nombre binaire donné, le nombre minimum d'opérations égal au nombre de bits plus le nombre de 1 dans la représentation binaire, moins 1.

Programme solución

#include <iostream>
using namespace std;

int main() {
    int tests;
    cin >> tests;
    
    while (tests--) {
        int longueur;
        cin >> longueur;
        
        int operationsMin = 0;
        
        for (int i = 0; i < longueur; ++i) {
            int nombre, operations = 0;
            cin >> nombre;
            
            while (nombre > 0) {
                operations += nombre % 2;
                nombre /= 2;
                operations++;
            }
            
            operationsMin = max(operationsMin, operations - 1);
        }
        
        cout << operationsMin << endl;
    }
    
    return 0;
}