Problèmes de Tournoi Éducatif Codeforces 171 (Div. 2)

A

Pour résoudre ce problème, il faut comprendre que pour maximiser la longueur minimale entre deux côtés, ces deux côtés doivent être égaux. Ainsi, nous construisons un carré dont le côté correspond à la valeur minimale entre x et y. La diagonale de ce carré représente la solution recherchée.

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

using namespace std;

int dimension1, dimension2, nbTests;

void resoudre()
{
    cin >> dimension1 >> dimension2 >> nbTests;
    int cote = min(dimension1, dimension2);
    cout << 0 << " " << 0 << " " << cote << " " << cote << endl;
    cout << 0 << " " << cote << " " << cote << " " << 0 << endl;
}

int main()
{
    #ifndef ONLINE_JUDGE 
    freopen("entree.in", "r", stdin);
    freopen("sortie.out", "w", stdout);
    #endif
    
    int T;
    cin >> T;
    while(T--) resoudre();
    return 0;
}

B

Lorsque n est pair, les nombres doivent être associés deux à deux et colorés en noir. La différence maximale entre ces paires détermine la valeur k. Pour n impair, il est nécessaire d'identifier un nombre qui ne s'associe à aucun autre, puis de traiter les deux segments restants séparément, en appliquant la même logique que dans le cas pair.

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

using namespace std;
typedef long long ll;

const int MAX = 2005;
const ll INFINI = 1e18;

int quantite;
ll valeurs[MAX];

void resoudre()
{
    cin >> quantite;
    for(int i = 1; i <= quantite; i++) {
        cin >> valeurs[i];
    }
    
    ll resultat = INFINI;
    ll diffMax;
    
    if(quantite % 2 == 1) {
        for(int i = 1; i <= quantite; i += 2) {
            diffMax = 0;
            for(int j = 1; j < i; j += 2) {
                diffMax = max(diffMax, valeurs[j+1] - valeurs[j]);
            }
            for(int j = i+1; j <= quantite; j += 2) {
                diffMax = max(diffMax, valeurs[j+1] - valeurs[j]);
            }
            resultat = min(resultat, diffMax);
        }
        cout << max(1LL, resultat) << endl;
    } else {
        diffMax = 0;
        for(int i = 2; i <= quantite; i += 2) {
            diffMax = max(diffMax, valeurs[i] - valeurs[i-1]);
        }
        cout << diffMax << endl;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE 
    freopen("entree.in", "r", stdin);
    freopen("sortie.out", "w", stdout);
    #endif
    
    int T;
    cin >> T;
    while(T--) resoudre();
    return 0;
}

C

Pour optimiser les réductions, nous adoptons une approche gloutonne en privilégiant de maximiser les remises sur les articles ultérieurs. Les articles avec une valeur de 0 ne peuvent bénéficier de réduction. Nous utilisons une double file d'attente pour stocker les positions des articles à 1, en essayant de les associer avec des articles à 0 ou d'autres articles à 1 pour obtenir le maximum de réductions possiblse.

#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;

const int MAX = 4e5 + 5;

int longueur;
string sequence;
deque<int> fileAttente;
int positions[MAX], totalPositions;
ll totalReductions;

void resoudre()
{
    cin >> longueur;
    cin >> sequence;
    totalPositions = totalReductions = 0;
    
    for(int i = 0; i < longueur; i++) {
        if(sequence[i] == '1') {
            fileAttente.push_back(i+1);
        } else {
            positions[++totalPositions] = i+1;
        }
        totalReductions += i+1;
    }
    
    while(!fileAttente.empty()) {
        int actuel = fileAttente.back();
        fileAttente.pop_back();
        
        while(totalPositions > 0 && positions[totalPositions] > actuel) {
            totalPositions--;
        }
        
        if(totalPositions > 0) {
            totalPositions--;
            totalReductions -= actuel;
        } else {
            if(!fileAttente.empty()) {
                fileAttente.pop_front();
                totalReductions -= actuel;
            }
        }
    }
    
    cout << totalReductions << endl;
}

int main()
{
    #ifndef ONLINE_JUDGE 
    freopen("entree.in", "r", stdin);
    freopen("sortie.out", "w", stdout);
    #endif
    
    int T;
    cin >> T;
    while(T--) resoudre();
    return 0;
}

D

Ce problème mathématique s'est avéré complexe et n'a pas été résolu lors de la compétition.