Problema J: Simulação de Pontuação

Este problema exige uma simulação direta baseada em uma sequência de caracteres. Cada caractere altera o estado de uma variável de valor e contribui para o resultado acumulado.

Regras de transição:

• '0': Aumenta o valor atual em 10 e adiciona ao total.
• '1': Reduz o valor atual em 5 (mínimo 0) e adiciona ao total.
• Outros: Se o valor for pelo menos 10, adiciona (valor - 10) ao total. Caso contrário, não faz nada.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void processar_pontuacao() {
    int tam;
    string seq;
    cin >> tam >> seq;
    
    long long total = 0;
    int pts_atuais = 0;
    
    for (char c : seq) {
        if (c == '0') {
            pts_atuais += 10;
            total += pts_atuais;
        } else if (c == '1') {
            pts_atuais = max(0, pts_atuais - 5);
            total += pts_atuais;
        } else {
            if (pts_atuais >= 10) {
                total += (pts_atuais - 10);
            }
        }
    }
    cout << total << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    processar_pontuacao();
    return 0;
}

Problema B: Divisão de Madeira

O objetivo é dividir um bloco de comprimento $n$ em pedaços de tamanho mínimo $t$, respeitando um limite de $k$ cortes. Cada corte ocupa 1 unidade de comprimento.

Estratégia ambiciosa (Greedy): Para maximizar o número de pedaços, cada pedaço deve ter o tamanho mínimo permitido. O número máximo de pedaços é limitado tanto pelo comprimento disponível quanto pelo número de cortes permitidos ($k+1$).

#include <iostream>
#include <algorithm>

using namespace std;

void resolver_madeira() {
    long long n, t, k;
    cin >> n >> t >> k;
    
    long long espaco_util = n - k;
    if (espaco_util < t) {
        cout << 0 << endl;
        return;
    }
    
    long long possiveis = espaco_util / t;
    cout << min(possiveis, k + 1) << endl;
}

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

Problema I: Verificação Binária

Um problema de observação onde o resultado depende da presença de zeros em $n$ ou $m$. Se ambos forem zero, a resposta é positiva. Se apenas um for zero, é negativa. Em todos os outros casos, assume-se "Yes".

#include <iostream>

using namespace std;

void verificar_estado() {
    int n, m;
    cin >> n >> m;
    if (n == 0 || m == 0) {
        cout << (n == m ? "Yes" : "No") << endl;
    } else {
        cout << "Yes" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) verificar_estado();
    return 0;
}

Problema E: Análise de Jogo 3x3

Verifica se um jogador (X) pode vencer em um tabuleiro 3x3. A lógica foca em contar as peças em cada linha, coluna e diagonal. Se uma linha não contém peças do oponente (O) e possui pelo menos uma peça X, ela é uma candidata a vitória dependendo do número de movimentos realizados.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void analisar_tabuleiro() {
    vector<string> grade(3);
    int total_pecas = 0;
    vector<int> lin(3, 0), col(3, 0);
    int diag1 = 0, diag2 = 0;

    for (int i = 0; i < 3; ++i) {
        cin >> grade[i];
        for (int j = 0; j < 3; ++j) {
            if (grade[i][j] == 'G') continue;
            total_pecas++;
            int val = (grade[i][j] == 'X') ? 1 : -10;
            lin[i] += val;
            col[j] += val;
            if (i == j) diag1 += val;
            if (i + j == 2) diag2 += val;
        }
    }

    bool chance_vitoria = false;
    for (int i = 0; i < 3; ++i) {
        if (lin[i] > 0 || col[i] > 0) chance_vitoria = true;
    }
    if (diag1 > 0 || diag2 > 0) chance_vitoria = true;

    if (total_pecas / 2 <= 2 || chance_vitoria) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) analisar_tabuleiro();
    return 0;
}

Problema C: Otimização de Operações Bitwise

O desafio é transformar strings binárias usando operações de inversão (custo $x$) ou troca (custo $y$). O segredo é contar as discrepâncias em relação ao resultado esperado para cada combinação possível de bits (00, 01, 10, 11) nas strings originais.

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

using namespace std;

typedef long long ll;

void otimizar_bits() {
    int n;
    ll x, y;
    string a, b, c;
    cin >> n >> x >> y;
    cin >> a >> b >> c;

    ll tipos[4] = {0, 0, 0, 0};
    for (int i = 0; i < n; ++i) {
        int atual = (a[i] == b[i] ? 0 : 1);
        if (c[i] - '0' == atual) continue;
        
        if (a[i] == '0' && b[i] == '0') tipos[0]++;
        else if (a[i] == '0' && b[i] == '1') tipos[1]++;
        else if (a[i] == '1' && b[i] == '0') tipos[2]++;
        else tipos[3]++;
    }

    ll total_diff = tipos[0] + tipos[1] + tipos[2] + tipos[3];
    ll custo_base = total_diff * x;
    
    sort(tipos, tipos + 4);
    ll max_tipo = tipos[3];
    ll outros = total_diff - max_tipo;

    if (max_tipo > outros) {
        custo_base = min(custo_base, outros * y + (max_tipo - outros) * x);
    } else {
        custo_base = min(custo_base, (total_diff / 2) * y + (total_diff % 2) * x);
    }
    
    cout << custo_base << endl;
}

int main() {
    otimizar_bits();
    return 0;
}

Problema L: Construção de Tripletos Coprimos

O problema solicita a formação de tripletos onde exatamente dois pares são coprimos entre si. A construção utiliza propriedades de números consecutivos e padrões de repetição a cada 6 unidades para cobrir o intervalo até $n$.

#include <iostream>

using namespace std;

void construir_tripletos() {
    int n;
    cin >> n;
    if (n < 4) {
        cout << 0 << endl;
        return;
    }
    
    cout << n / 3 << endl;
    if (n < 6) {
        cout "2 3 4" << endl;
        return;
    }

    if ((n / 3) % 2 == 0) {
        for (int i = 1; i + 5 <= n; i += 6) {
            cout << i << " " << i + 1 << " " << i + 3 << "\n";
            cout << i + 2 << " " << i + 4 << " " << i + 5 << "\n";
        }
    } else {
        cout << "1 2 4\n3 9 5\n6 8 7\n";
        for (int i = 10; i + 5 <= n; i += 6) {
            cout << i + 1 << " " << i + 2 << " " << i + 5 << "\n";
            cout << i << " " << i + 3 << " " << i + 4 << "\n";
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) construir_tripletos();
    return 0;
}

Problema D: Contribuição de Intervalos

Neste problema, analisamos o impacto de reorganizar bits em janelas de tamanho $k$. A contribuição de cada janela para o resultado final depende da uniformidade dos bits dentro dela. Usamos somas de prefixo para determinar rapidamente se um intervalo contém tanto '0's quanto '1's.

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

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + (s[i] == '1');
    }
    
    int xor_resultado = 0;
    for (int k = 1; k <= n; ++k) {
        int contagem = 1;
        for (int i = 1; i <= n; i += k) {
            int esq = i, dir = min(n, i + k - 1);
            int uns = pref[dir] - pref[esq - 1];
            int total = dir - esq + 1;
            if (uns > 0 && uns < total) {
                contagem++;
            }
        }
        xor_resultado ^= contagem;
    }
    cout << xor_resultado << endl;
    return 0;
}