A. Processamento de Ingredientes (Zhan's Blender)

Para determinar a quantidade mínima de iterações necessárias para processar todos os n itens disponíveis, observamos que cada ciclo opera com no máximo min(x, y) unidades. A solução matemática direta corresponde ao teto da divisão inteira entre o total desejado e a capacidade efetiva por etapa. Implementamos essa lógica utilizando aritmética de inteiros para evitar imprecisões de ponto flutuante, garantindo precisão e eficiência O(1).

using namespace std; typedef long long ll;

void solve() { ll total_itens, capacidade_a, capacidade_b; cin >> total_itens >> capacidade_a >> capacidade_b;

// Capacidade máxima processável por rodada
ll limite = min(capacidade_a, capacidade_b);

// Cálculo exato de ceil(total_itens / limite) usando aritmética inteira
ll rodadas = (total_itens + limite - 1) / limite;

cout << rodadas << '\n';

}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);

int casos_teste;
cin >> casos_teste;
while (casos_teste--) {
    solve();
}
return 0;

}

</div>---

B. Maximização do Último Elemento (Battle for Survive)
------------------------------------------------------

O cenário envolve uma sequência numérica onde operamos subtrações sequenciasi para preservar o maior valor possível no último termo. A aálise estrutural revela que acumular a soma de todos os elementos anteriores ao penúltimo, subtrair o penúltimo e somar ao último resulta na configuração ótima. Essa abordagem evita cálculos intermediários desnecessários e mantém a complexidade linear O(N), adequada para grandes vetores.

<div class="code-block">```
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

void resolver_caso() {
    int n;
    cin >> n;
    
    vector<ll> valores(n);
    ll soma_acumulada = 0;
    
    for (int i = 0; i < n; ++i) {
        cin >> valores[i];
        // Acumula apenas os elementos que antecedem o par (penúltimo, último)
        if (i < n - 2) {
            soma_acumulada += valores[i];
        }
    }
    
    // Fórmula derivada da dinâmica ótimo: último - penúltimo + soma_anterior
    ll resultado_final = valores[n - 1] - valores[n - 2] + soma_acumulada;
    cout << resultado_final << '\n';
}

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

C. Reconstrução Interativa de Senhas (Password Cracking)

Este é um desafio interativo onde o sistema valida parcialmente strings binárias contra um alvo oculto de comprimento n. A estratégia eficiente inicia consultando padrões unitários para estabelecer um ponto de partida válido. Em seguida, o algoritmo tenta expandir a string candidata pela direita. Se nenhuma extensão for aceita antes de atingir o tamanho meta, o fluxo se inverte e realiza tentativas de pré-adição. O controle rigoroso das mensagens e flush de stream garante conformidade com o protocolo de avaliação.

using namespace std;

// Função padrão de interação conforme especificação da plataforma int consultar(const string& tentativa) { cout << "? " << tentativa << "\n"; cout.flush(); int retorno; cin >> retorno; return retorno; }

void resolver_interativo() { int n; cin >> n;

string candidato;

// Verificação inicial dos dígitos isolados
int res_zero = consultar("0");
int res_um   = consultar("1");

if (res_zero == n) { cout << "! 0\n"; return; }
if (res_um == n)   { cout << "! 1\n"; return; }

// Define base conforme maior compatibilidade detectada
candidato = (res_zero > res_um) ? "0" : "1";

// Tentativa de expansão direita-esquerda
while (static_cast<int>(candidato.size()) < n) {
    string exp0 = candidato + '0';
    string exp1 = candidato + '1';
    
    int val0 = consultar(exp0);
    if (val0 == n) { candidato = exp0; break; }
    
    int val1 = consultar(exp1);
    if (val1 == n) { candidato = exp1; break; }
    
    // Progresso conservador caso ambas falhem parcialmente
    candidato = (val0 > 0) ? exp0 : exp1;
    if (static_cast<int>(candidato.size()) == n) break;
}

// Fallback: pré-adicionar quando extensão direta bloqueia
while (static_cast<int>(candidato.size()) < n) {
    string pre0 = '0' + candidato;
    string pre1 = '1' + candidato;
    
    int rv0 = consultar(pre0);
    if (rv0 == n) { candidato = pre0; break; }
    
    int rv1 = consultar(pre1);
    if (rv1 == n) { candidato = pre1; break; }
    
    candidato = (rv0 > rv1) ? pre0 : pre1;
}

cout << "! " << candidato << "\n";

}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);

int testes;
cin >> testes;
while (testes--) {
    resolver_interativo();
}
return 0;

}

</div>---

E. Redução Gradual de GCD Prefixal (Prefix GCD)
-----------------------------------------------

A construção de um prefixo com GCD decrescente exige planejamento estrutural. Inicialmente, ordenamos o conjunto e fixamos o menor elemento como raiz restritiva. O objetivo é reduzir progressivamente o GCD acumulativo até atingir o mínimo global possível. Utilizamos um crivo pré-computado para fatoração rápida (`O(log V)`) e um mecanismo guloso que seleciona, a cada passo, o componente não utilizado que compartilha o maior produto de fatores primários necessários para baixar o currentValue. Quando o alvo é alcançado, completamos o prefixo restente multiplicando pelas ocorrências finais, mantendo a complexidade próxima de `O(N log N)`.

<div class="code-block">```
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

const int LIMITE_VALOR = 100005;
int spf[LIMITE_VALOR]; // Smallest Prime Factor

void construir_crivo() {
    for (int i = 0; i < LIMITE_VALOR; ++i) spf[i] = i;
    for (int i = 2; i * i < LIMITE_VALOR; ++i) {
        if (spf[i] == i) {
            for (int j = i * i; j < LIMITE_VALOR; j += i)
                if (spf[j] == j) spf[j] = i;
        }
    }
}

ll calcular_gcd(ll a, ll b) {
    while (b) {
        ll tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

void resolver() {
    int n;
    cin >> n;
    
    vector<ll> array_num(n);
    ll gcd_global = 0;
    
    for (int i = 0; i < n; ++i) {
        cin >> array_num[i];
        gcd_global = calcular_gcd(gcd_global, array_num[i]);
    }

    sort(array_num.begin(), array_num.end());
    vector<bool> ocupado(n, false);
    
    ll gcd_atual = array_num[0];
    ocupado[0] = true;
    ll soma_prefixo = gcd_atual;
    
    auto extrair_fatores = [&](ll valor, map<ll, int>& mapa) {
        while (valor > 1) {
            int p = spf[valor];
            int expoente = 0;
            while (valor % p == 0) {
                valor /= p;
                expoente++;
            }
            mapa[p] = expoente;
        }
    };
    
    while (gcd_atual > gcd_global) {
        map<ll, int> necessario;
        extrair_fatores(gcd_atual, necessario);
        
        int melhor_indice = -1;
        ll maior_produto_compartilhado = 0;
        
        for (int i = 1; i < n; ++i) {
            if (ocupado[i]) continue;
            
            map<ll, int> fatores_candidato;
            extrair_fatores(array_num[i], fatores_candidato);
            
            ll produto_relevante = 1;
            for (auto const& [primo, qtd_neces] : necessario) {
                if (fatores_candidato.count(primo)) {
                    int qtd_tem = fatores_candidato[primo];
                    int pegar = min(qtd_tem, qtd_neces);
                    for (int k = 0; k < pegar; ++k) produto_relevante *= primo;
                }
            }
            
            if (produto_relevante > maior_produto_compartilhado) {
                maior_produto_compartilhado = produto_relevante;
                melhor_indice = i;
            }
        }
        
        if (melhor_indice == -1) break;
        
        ocupado[melhor_indice] = true;
        gcd_atual = calcular_gcd(gcd_atual, array_num[melhor_indice]);
        soma_prefixo += gcd_atual;
    }
    
    int contador_usados = 0;
    for (bool vis : ocupado) if (vis) contador_usados++;
    
    soma_prefixo += static_cast<ll>(n - contador_usados) * gcd_global;
    cout << soma_prefixo << '\n';
}

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