A. Centro de Reciclagem

O problema permite uma abordagem gulosa dada a restrição de tamanho reduzido para o número de sacos. A estratégia consiste em iterativamente selecionar o saco mais pesado que ainda cabe na capacidade atual c. Ao utilizar um saco, os custos dos itens remanescentes são duplicados, simulando a penalidade de espaço acumulada. Quando nenhum saco restante satisfaz a condição de peso, cada unidade residual exige uma moeda adicional.

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

using namespace std;

void resolver() {
    int n;
    long long capacidade;
    cin >> n >> capacidade;
    
    vector<long long> pesos(n);
    vector<bool> utilizado(n, false);
    for (int i = 0; i < n; ++i) cin >> pesos[i];

    long long moedas_necessarias = 0;
    int restantes = n;

    while (true) {
        int idx_melhor = -1;
        // Identifica o maior peso viável não consumido
        for (int i = 0; i < n; ++i) {
            if (!utilizado[i] && pesos[i] <= capacidade) {
                if (idx_melhor == -1 || pesos[i] > pesos[idx_melhor]) {
                    idx_melhor = i;
                }
            }
        }

        if (idx_melhor != -1) {
            utilizado[idx_melhor] = true;
            restantes--;
            
            // Aplica a penalidade de custo aos itens não marcados
            for (int i = 0; i < n; ++i) {
                if (!utilizado[i]) pesos[i] *= 2;
            }
        } else {
            // Não há mais itens compatíveis; converte todos os restantes
            moedas_necessarias += restantes;
            break;
        }
    }
    cout << moedas_necessarias << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qtd_testes;
    cin >> qtd_testes;
    while (qtd_testes--) resolver();
    return 0;
}

B. Processo com Fila Dupla

A construção ótima segue um padrão oscilante nas extremidades da estrutura. Como os valores nas pontas esquerda e direita diferem sistematicamente, alternar entre escolher o máximo e o mínimo preserva a propriedade solicitada pelo enunciado. A implementação utiliza dois ponteiros para percorrer o vetor, decidindo a direção baseada na paridade do turno atual.

#include <iostream>
#include <vector>

using namespace std;

void resolver() {
    int n;
    cin >> n;
    vector<int> dados(n);
    for (int i = 0; i < n; ++i) cin >> dados[i];

    int esq = 0, dir = n - 1;
    string padrao = "";

    for (int turno = 0; turno < n; ++turno) {
        bool extrair_esquerda;
        // Alternância: pares buscam maior, ímpares buscam menor
        if (turno % 2 == 0) {
            extrair_esquerda = (dados[esq] >= dados[dir]);
        } else {
            extrair_esquerda = (dados[esq] <= dados[dir]);
        }

        if (extrair_esquerda) {
            padrao += 'L';
            esq++;
        } else {
            padrao += 'R';
            dir--;
        }
    }
    cout << padrao << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qtd_testes;
    cin >> qtd_testes;
    while (qtd_testes--) resolver();
    return 0;
}

C. Esquerda Abaixo

A validade da configuração depende esrtitamente de limites cumulativos impostas pela ordem mínima de incremento. Para cada posição, verifica-se se o alvo excede a restrição atual. Caso contrário, ajusta-se o limite com base na paridade do valor desejdao, garantindo que a progressão aritmética implícita não viole as condições anteriores.

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

using namespace std;

void resolver() {
    int n;
    cin >> n;
    vector<long long> alvo(n);
    for (int i = 0; i < n; ++i) cin >> alvo[i];

    long long limite_atual = 1e18;
    bool valido = true;

    for (int i = 0; i < n; ++i) {
        if (alvo[i] > limite_atual) {
            bool viola_limite = false;
            if (alvo[i] % 2 != 0) {
                if ((alvo[i] / 2) > limite_atual || (alvo[i] / 2 + 1) > limite_atual)
                    viola_limite = true;
            } else {
                if ((alvo[i] / 2 - 1) > limite_atual || (alvo[i] / 2 + 1) > limite_atual)
                    viola_limite = true;
            }
            if (viola_limite) {
                valido = false;
                break;
            }
        }
        limite_atual = min(limite_atual, alvo[i]);
    }
    cout << (valido ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qtd_testes;
    cin >> qtd_testes;
    while (qtd_testes--) resolver();
    return 0;
}

D. Soma da Subseção Decrescente

A restrição max(p[i-2], p[i-1]) > p[i] limita as extensões possíveis, permitindo que apenas as duas posições imediatas anteriores sejam consideradas como origem das sequências. Define-se dp[i] como o número de arranjos válidos terminados em i. As transições somam o acúmulo anterior acrescido do número de opções de início de subseção, combinando casos base e estendidos.

#include <iostream>
#include <vector>

using namespace std;

void resolver() {
    int n;
    cin >> n;
    vector<int> seq(n + 1);
    for (int i = 1; i <= n; ++i) cin >> seq[i];

    vector<long long> dp(n + 1, 0);
    long long acumulador_total = 0;

    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            dp[i] = 1;
        } else if (i == 2) {
            if (seq[i - 1] > seq[i]) dp[i] = dp[i - 1] + 2;
            else dp[i] = 2;
        } else {
            dp[i] = 0;
            // Extensão direta do índice anterior
            if (seq[i - 1] > seq[i]) dp[i] = dp[i - 1] + i;
            // Extensão pulando um índice
            if (seq[i - 2] > seq[i]) dp[i] = max(dp[i], dp[i - 2] + i);
        }
        acumulador_total += dp[i];
    }
    cout << acumulador_total << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qtd_testes;
    cin >> qtd_testes;
    while (qtd_testes--) resolver();
    return 0;
}

E1. Submediana (Versão Fácil)

A solução combina busca binária sobre o intervalo de respostas com verificação linear. Para cada candidato médio, transforma-se o vetor em sinais positivos e negativos. Utiliza-se pré-somas combinadas com vetores de extensão máxima à esquerda e à direita para determinar se existe algum intervalo de comprimento ≥ k cuja soma seja não negativa. Após encontrar o valor ótimo, reconstrói-se a janela válida varrendo o array até a primeira ocorrência que satisfaça a condição.

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

using namespace std;

void resolver() {
    int n, k;
    cin >> n >> k;
    vector<int> elementos(n + 1);
    for (int i = 1; i <= n; ++i) cin >> elementos[i];

    auto verificar_candidato = [&](int pivô) -> pair<bool, int> {
        vector<int> ext_esq(n + 2, 0), ext_dir(n + 2, 0), prefixo(n + 2, 0);
        
        for (int i = 1; i <= n; ++i) {
            int sinal = (elementos[i] >= pivô) ? 1 : -1;
            ext_esq[i] = max(ext_esq[i - 1] + sinal, 0);
            prefixo[i] = prefixo[i - 1] + sinal;
        }
        for (int i = n; i >= 1; --i) {
            int sinal = (elementos[i] >= pivô) ? 1 : -1;
            ext_dir[i] = max(ext_dir[i + 1] + sinal, 0);
        }

        int primeira_ocorrencia = -1;
        for (int i = 1; i <= n - k + 1; ++i) {
            int j = i + k - 1;
            int soma_janela = prefixo[j] - prefixo[i - 1];
            int potencial_expansao = ext_esq[i - 1] + ext_dir[j + 1];
            
            if (soma_janela + potencial_expansao >= 0) {
                if (primeira_ocorrencia == -1) primeira_ocorrencia = i;
            }
        }
        return {primeira_ocorrencia != -1, primeira_ocorrencia};
    };

    int infimo = 1, supremo = n, resposta_final = -1, indice_inicio = -1;
    while (infimo <= supremo) {
        int meio = infimo + (supremo - infimo) / 2;
        auto [encontrou, pos] = verificar_candidato(meio);
        if (encontrou) {
            resposta_final = meio;
            indice_inicio = pos;
            infimo = meio + 1;
        } else {
            supremo = meio - 1;
        }
    }

    int lim_inf = (indice_inicio != -1) ? indice_inicio : 1;
    int lim_sup = -1;
    int soma_acumulada = 0;

    for (int i = lim_inf; i <= n; ++i) {
        soma_acumulada += (elementos[i] >= resposta_final ? 1 : -1);
        if ((i - lim_inf + 1) >= k && soma_acumulada >= 0) {
            lim_sup = i;
            break;
        }
    }
    cout << resposta_final << " " << lim_inf << " " << lim_sup << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int qtd_testes;
    cin >> qtd_testes;
    while (qtd_testes--) resolver();
    return 0;
}