Problema A: Brick Wall

Neste problema, temos uma parede de dimensões \(n \times m\) e uma quantidade ilimitada de tijolos de tamanho \(1 \times x\), onde \(x \ge 2\). O objetivo é preencher a parede completamente. A estabilidade da parede é calculada somando-se 1 para cada tijolo colocado horizontalmente e subtraindo-se 1 para cada tijolo na vertical. Devemos encontrar a estabilidade máxima possível.

Para maximizar esse valor, a estratégia ideal é utilizar apenas tijolos horizontais e garantir que eles sejam o menor possível, ou seja, de tamanho \(1 \times 2\). Dessa forma, maximizamos a quantidade de tijolos por linha. Se uma linha tiver largura \(m\), podemos colocar \(\lfloor m/2 \rfloor\) tijolos horizontais nela. Multiplicando pelo número de linhas \(n\), obtemos o resultado máximo.

#include <iostream>

void processar_caso() {
    long long linhas, colunas;
    if (!(std::cin >> linhas >> colunas)) return;
    
    // Maximiza-se a estabilidade usando tijolos 1x2 na horizontal
    long long resultado = (colunas / 2) * linhas;
    std::cout << resultado << std::endl;
}

Problema B: Minimize Inversions

São fornecidos dois arrays, \(a\) e \(b\), ambos de comprimento \(n\). Podemos realizar operações de troca nos elementos, mas qualquer troca de posição nos índices \(i\) e \(j\) deve ser aplicada simultaneamente em ambos os arrays. O objetivo é minimizar a soma total de inversões nos dois arrays resultantes.

A solução reside na observação de que, ao ordenar completamente um dos arrays, reduzimos suas inversões a zero. Como as trocas são vinculadas, ao ordenar o array \(a\), o array \(b\) assumirá uma configuração que tende a ter o menor número de inversões possível em relação à ordem de \(a\). Portanto, basta criar pares \((a_i, b_i)\), ordená-los com base no pirmeiro elemento e imprimir os arrays reorganizados.

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

void resolver_inversoes() {
    int tamanho;
    std::cin >> tamanho;
    std::vector<std::pair<int, int>> pares(tamanho);

    for (int i = 0; i < tamanho; ++i) std::cin >> pares[i].first;
    for (int i = 0; i < tamanho; ++i) std::cin >> pares[i].second;

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

    for (int i = 0; i < tamanho; ++i) 
        std::cout << pares[i].first << (i == tamanho - 1 ? "" : " ");
    std::cout << "\n";

    for (int i = 0; i < tamanho; ++i) 
        std::cout << pares[i].second << (i == tamanho - 1 ? "" : " ");
    std::cout << "\n";
}

Problema C: XOR-distance

Dados três inteiros \(a, b\) e \(r\), precisamos encontrar um valor \(x\) tal que \(0 \le x \le r\) que minimize o valor de \(|(a \oplus x) - (b \oplus x)|\).

Como os valores podem chegar a \(10^{18}\), utilizamos uma abordagem gananciosa (greedy) bit a bit. Primeiro, garantimos que \(a \ge b\). Analisamos os bits do mais significaitvo para o menos significativo. O primeiro bit onde \(a\) e \(b\) diferem (onde \(a\) tem 1 e \(b\) tem 0) define que \(a \oplus x\) será maior que \(b \oplus x\). Para todos os bits subsequentes onde \(a\) possui 1 e \(b\) possui 0, tentamos inverter esse bit usando \(x\) (atribuindo 1 ao bit correspondente de \(x\)), desde que o valor acumulado de \(x\) não ultrapasse o limite \(r\). Isso aproxima os dois valores e minimiza a diferença absoluta.

#include <iostream>
#include <cmath>

typedef long long ll;

void calcular_xor_distancia() {
    ll v1, v2, limite;
    std::cin >> v1 >> v2 >> limite;

    if (v1 < v2) std::swap(v1, v2);

    ll ajuste_x = 0;
    bool primeiro_bit_encontrado = false;

    for (int bit = 60; bit >= 0; --bit) {
        bool bit_a = (v1 >> bit) & 1;
        bool bit_b = (v2 >> bit) & 1;

        if (bit_a != bit_b) {
            if (!primeiro_bit_encontrado) {
                primeiro_bit_encontrado = true;
            } else {
                // Se o bit de v1 é 1 e de v2 é 0, tentamos virar para reduzir a diferença
                if (bit_a && (ajuste_x + (1LL << bit) <= limite)) {
                    ajuste_x |= (1LL << bit);
                }
            }
        }
    }

    ll diff = std::abs((v1 ^ ajuste_x) - (v2 ^ ajuste_x));
    std::cout << diff << std::endl;
}