A. Jeu de combinaison

Problème original : CF1221A

Énoncé :

Xiao Hua adore jouer à 2048 et partage maintenant une version 2048pro avec vous. Pouvez-vous réussir à atteindre 2048 ?

Initialement, vous avez un ensemble S de n entiers. Chaque entier de cet ensemble est une puissance de 2 (1, 2, 4, 8, 16, 32, ...).

Vous pouvez effectuer un nombre arbitraire d'opérations (y compris zéro) sur cet ensemble.

Dans chaque opération, vous sélectionnez deux entiers égaux dans S, les retirez de S et insérez leur somme dans S.

Par exemple, si S = {1, 2, 1, 1, 4, 2, 2}, et que vous choisissez de retirer (2, 2), alors l'ensemble devient {1, 1, 1, 4, 4, 2}.

Après un certain nombre d'opérations, si le nombre 2048 est présent dans l'ensemble S, vous avez gagné.

Entrée La première ligne contient un entier q (1 ≤ q ≤ 100) - le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier n (1 ≤ n ≤ 100) - le nombre d'éléments dans S.

La deuxième ligne contient n entiers s₁, s₂, ..., sₙ (1 ≤ sᵢ ≤ 2²⁹) - les éléments de l'ensemble S. On garantit que tous les éléments de S sont des puissances de 2.

Sortie Pour chaque cas de test, si il est possible d'obtenir le nombre 2048, affichez OUI sinon affichez NON

Explication des exemples

Dans le premier cas de test, vous pouvez gagner comme suit : choisissez (512, 512), S devient {1024, 64, 1024}. Ensuite, choisissez (1024, 1024), S devient {2048, 64} et vous gagnez.

Dans le deuxième cas de test, S contient initialement 2048.

Solution :

Approche : Utiliser une file de priorité pour simuler les opérations de manière efficace.

#define OUI cout << "OUI" << endl;
#define NON cout << "NON" << endl;

void resoudre()
{
    priority_queue<int, vector<int>, greater<int>> file;  // File de priorité avec le plus petit élément en premier
    int nbTests;
    cin >> nbTests;
    
    while(nbTests--)
    {
        while(!file.empty()) file.pop();  // Vider la file
        int nbElements;
        cin >> nbElements;
        
        for(int i = 0; i < nbElements; i++)
        {
            int valeur; 
            cin >> valeur; 
            file.push(valeur);
        }
        
        while(true)
        {
            int premier = file.top(); 
            file.pop();  // Extraire le plus petit élément
            
            if(premier == 2048)
            {
                OUI;
                break;
            }
            
            if(premier > 2048 || file.empty()) 
            {
                NON;
                break;
            }
            
            if(premier == file.top())  // Si les deux plus petits éléments sont égaux
            {
                int second = file.top();
                file.pop();
                file.push(premier * 2);
                
                if(second == 2048)
                {
                    OUI;
                    break;
                }
            }
        }
    }
}

B. Séquence ordonnée

Problème original : CF920C

Xiao Hua adore les séquences strictement croissantes. Pouvez-vous l'aider ?

Vous avez un tableau A composé de n entiers. Chaque entier de 1 à n n'apparaît qu'une fois dans ce tableau.

Autrement dit, les éléments du tableau A forment une permutation de 1 à n.

Pour chaque indice i (1 ≤ i ≤ n - 1), vous pouvez échanger l'élément à la position i avec l'élément à la position (i + 1). Pour les autres indices, l'échange n'est pas autorisé. Vous pouvez effectuer un nombre arbitraire d'échanges. Le nombre d'échanges entre l'élément à la position i et l'élément à la posittion (i + 1) n'est pas limité (si cet échange n'est pas interdit).

Pouvez-vous, par une série d'échanges, trier ce tableau par ordre croissant ?

Entrée La première ligne contient un entier n (2 ≤ n ≤ 200000) - le nombre d'éléments du tableau.

La deuxième ligne contient n entiers a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ 200000) - les éléments du tableau. Chaque entier de 1 à n apparaît exactement une fois.

La troisième ligne contient une chaîne de n - 1 caractères, chacun étant '0' ou '1'. Si le ième caractère est '1', alors l'élément à la position i peut être échangé avec l'élément à la position (i + 1) un nombre arbitraire de fois, sinon cet échange est interdit.

Sortie Si vous pouvez trier le tableau par ordre croissant par une série d'échanges, affichez OUI. Sinon, affichez NON.

Explication des exemples

Dans le premier exemple, vous pouvez d'abord échanger 5 et 3, puis échanger 4 et 5 pour obtenir une séquence ordonnée.

Solution :

Approche : Algorithme glouton.

Puisque les éléments du tableau A forment une permutation de 1 à n, la séquence croissante souhaitée est (1, 2, 3, ..., n). On peut démontrer que dans un segment continu d'indices où les échanges sont autorisés, on peut réarranger librement les éléments de ce segment. Ainsi, lorsque l'on atteint une position où aucun échange n'est autorisé, il suffit de vérifier si le maximum de la séquence traitée jusqu'à ce point correspond à la valeur attendue dans la séquence croissante.

#define OUI cout << "OUI" << endl;
#define NON cout << "NON" << endl;

const int TAILLE_MAX = 2e5 + 10;
int tableau[TAILLE_MAX];

void resoudre()
{
    int n, maximum = 0;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> tableau[i];
    
    string contraintes;
    cin >> contraintes;
    
    for (int i = 0; i < n-1; i++)
    {
        maximum = max(maximum, tableau[i]);  // Mettre à jour le maximum de la séquence actuelle
        
        if(contraintes[i] == '0' && i+1 != maximum)  // Vérifier si on ne peut pas construire la séquence souhaitée
        {
            NON;
            return;
        }
    }
    
    OUI;
}

void resoudre()
{
    int n, k = 3;
    if(n % 2 == 1)
    {
        cout << 1 << " " << n/2 << " " << n/2 << endl;
    }
    else if( (n/2) % 2 == 1 )
    {
        cout << 2 << " " << n/2-1 << " "<< n/2-1 << endl;
    }
    else 
    {
        cout << n/2 << " " << n/4 << " " << n/4 << endl;
    }
}

void resoudre()
{
    int n, k;
    cin >> n >> k;
    
    // Ajout des (k-3) uns
    for(int i = 0; i < k-3; i++) 
        cout << 1 << " ";
    
    n -= (k-3);  // Ajustement de la somme restante
    
    // Traitement des 3 derniers nombres (même logique que la version simple)
    if(n % 2 == 1)
    {
        cout << 1 << " " << n/2 << " " << n/2 << endl;
    }
    else if( (n/2) % 2 == 1 )
    {
        cout << 2 << " " << n/2-1 << " "<< n/2-1 << endl;
    }
    else 
    {
        cout << n/2 << " " << n/4 << " " << n/4 << endl;
    }
}