Conteúdo dos Problemas

Os problemas abordam temas variados com complexidade crescente. T1 envolve manipulação de sequências binárias, T2 utiliza árvores binárias com operações matemáticas, T3 emprega travessia em grafos com detecção de ciclos, e T4 explora manipulação numérica com estratégias ótimas.

T1: Contagem de Inversões Binárias

Para transformar uma sequência binária em todos zeros seguidos de uns, cada inversão "10" requer uma operação. A solução conta ocorrências desse padrão no array.

#include <iostream>
using namespace std;

int main() {
    int comprimento;
    cin >> comprimento;
    int valores[comprimento];
    
    for (int i = 0; i < comprimento; i++) {
        cin >> valores[i];
    }
    
    int ocorrencias = 0;
    for (int j = 0; j < comprimento - 1; j++) {
        if (valores[j] == 1 && valores[j + 1] == 0) {
            ocorrencias++;
        }
    }
    
    cout << ocorrencias << endl;
    return 0;
}

T2: Máximo Divisor Comum em Árvore Binária

Dada uma árvore binária completa, calcula o MDC no caminho mais curto entre dois nós. A solução rastreia ancestrais até encontrar o ancestral comum mais próximo.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll calcular_mdc(ll x, ll y) {
    while (y != 0) {
        ll temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll num_nos, consultas;
    cin >> num_nos >> consultas;
    vector<ll> valores(num_nos + 1);
    
    for (ll i = 1; i <= num_nos; i++) {
        cin >> valores[i];
    }
    
    while (consultas--) {
        ll no_a, no_b;
        cin >> no_a >> no_b;
        vector<ll> ancestrais_a, ancestrais_b;
        
        while (no_a > 0) {
            ancestrais_a.push_back(no_a);
            no_a /= 2;
        }
        
        while (no_b > 0) {
            ancestrais_b.push_back(no_b);
            no_b /= 2;
        }
        
        ll ancestral = 1;
        ll indice = 0;
        ll limite = min(ancestrais_a.size(), ancestrais_b.size());
        
        while (indice < limite && ancestrais_a[ancestrais_a.size() - 1 - indice] == ancestrais_b[ancestrais_b.size() - 1 - indice]) {
            ancestral = ancestrais_a[ancestrais_a.size() - 1 - indice];
            indice++;
        }
        
        ll resultado = valores[ancestral];
        for (ll k = ancestrais_a.size() - indice; k < ancestrais_a.size(); k++) {
            resultado = calcular_mdc(resultado, valores[ancestrais_a[k]]);
        }
        
        for (ll k = ancestrais_b.size() - indice; k < ancestrais_b.size(); k++) {
            resultado = calcular_mdc(resultado, valores[ancestrais_b[k]]);
        }
        
        cout << resultado << "\n";
    }
    return 0;
}

T3: Caminhos em Grafo Direcionado

Calcula o número de caminhos entre dois nós em um grafo direiconado. Se detectar ciclos alcançáveis, retorna -1. Utiliza DFS com memorização.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;
const ll MOD = 702649740970;

vector<vector<int>> ligacoes;
vector<ll> memo;
vector<bool> estado_visita;
bool ciclo_detectado = false;

ll buscar_caminhos(int atual) {
    if (memo[atual] != -1) return memo[atual];
    
    ll total = 0;
    bool ciclo_local = false;
    
    for (int proximo : ligacoes[atual]) {
        if (memo[proximo] != -1) {
            total = (total + memo[proximo]) % MOD;
            continue;
        }
        if (estado_visita[proximo]) {
            ciclo_local = true;
            continue;
        }
        estado_visita[proximo] = true;
        total = (total + buscar_caminhos(proximo)) % MOD;
    }
    
    memo[atual] = total;
    if (ciclo_local && total > 0) ciclo_detectado = true;
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int num_nos, num_arestas;
    cin >> num_nos >> num_arestas;
    ligacoes.resize(num_nos + 1);
    
    for (int i = 0; i < num_arestas; i++) {
        int origem, destino;
        cin >> origem >> destino;
        ligacoes[origem].push_back(destino);
    }
    
    memo.assign(num_nos + 1, -1);
    estado_visita.assign(num_nos + 1, false);
    memo[num_nos] = 1;
    estado_visita[1] = true;
    
    buscar_caminhos(1);
    cout << (ciclo_detectado ? -1 : memo[1]) << endl;
    return 0;
}

T4: Transformação de Dígitos Ótima

Encontra o custo mínimo para transformar uma sequência numérica em outra através de adições nas extremidades. Divide a sequência em segmentos esquerdo e direito, calculando diferenças com tratamneto especial para empréstimos.

Propriedades-chave: 1) Adições permitidas apenas nas extremidades, 2) Zeros podem ser adicionados sem custo, 3) Modificações internas requerem propagação de operações. A solução compara sub-sequências invertidas à esquerda e originais à direita, ajustando para empréstimos quando dígitos são insuficientes.